565.1

遅くても確実に通すところから...。来年は速く解けるようになるといいな。

250

整数配列が与えられる。それぞれに対してコストが指定されており、現在の手持ちに加えることができる。現在の手持ちより大きい数に出会った場合は必ず手持ちに加えないといけない。先頭から順に整数配列を見るとき、最終的に支払うコストの最小値を答えよ、という問題。

コストがかなり小さいので、整数配列の読んでいる位置と支払ったコストを状態にして、手持ちの値の最大値を計算してやる。後は一番最後の値を読み終わったところで、支払ったコストとして可能な値を全部調べてやればいい。

500

A以上B以下の整数すべてを一個ずつ持っている状態から開始して、交互に任意の値を2以上の値で割るという操作を行う。先にできなくなった方が負けというルールで、先手プレイヤーが勝つようなAとBの組は、L以上R以下の範囲でいくつあるか答えよ、という問題。

結局は素因数分解したときの約数の数がGrundyNumberになるNimなので、L以上R以下の整数について取り敢えず計算してやる。この値の範囲が小さいので、現在のXORの値ごとに何通りあるかをDPしてってやるだけ。途中で負けパターンを累計してやって、全体から引いてやる。

1000

見てない。10分くらいは残して読みたいなぁ...。