2019JOI本選1 勇者ビ太郎 解説

問題リンク

解説

累積和の典型的な問題です。

まず、宝石の位置を固定すると解きやすくなる、というのは感覚的に明らかでしょう。オーブと金塊のあるべき位置の条件が定まるからです。 結局、宝石を決めたとき、その右側にオーブが何個あるか、下に金塊が何個あるかが高速に求められればよいです。宝石の位置は全探索できます。

ここで、右側から左側にオーブの個数の累積和を、上から下に金塊の累積和をとってやれば、上に挙げたふたつの数が で求められます。

これで、この問題を で解くことができました。

このレベルの累積和は実装が楽なことが多いので、素早く通したい問題のひとつです。