解説
累積和の典型的な問題です。
まず、宝石の位置を固定すると解きやすくなる、というのは感覚的に明らかでしょう。オーブと金塊のあるべき位置の条件が定まるからです。 結局、宝石を決めたとき、その右側にオーブが何個あるか、下に金塊が何個あるかが高速に求められればよいです。宝石の位置は全探索できます。
ここで、右側から左側にオーブの個数の累積和を、上から下に金塊の累積和をとってやれば、上に挙げたふたつの数が で求められます。
これで、この問題を で解くことができました。
このレベルの累積和は実装が楽なことが多いので、素早く通したい問題のひとつです。
