ABC201 D Game in Momotetsu World
まず, 差分をとる典型を用いる. あわせて偶奇性を考える. すると次のようなことがわかる. スコアの差分を考える. この値を$ sとおく.
マス$ (i, j)について, $ i + jが偶数の場合
青木くんがこのマスに動かす.
$ A_{i, j} = +の場合, $ sに$ -1を加算する.
$ A_{i, j} = -の場合, $ sに$ 1を加算する.
そうでない場合
高橋くんがこのマスに動かす.
$ A_{i, j} = +の場合, $ sに$ 1を加算する.
$ A_{i, j} = -の場合, $ sに$ -1を加算する.
このことがわかれば, あとはゲームは後ろから見ていくという典型を用いて, $ dp_{i, j} := マス$ (i, j)から始めた時の差分 としてDPをしていけばよい. 遷移は下のマス, 右のマスからを考えればよく, 高橋くんの移動の際は差分を最大化したいのでmax, 青木くんの移動の際は差分を最小化したいのでminをとればよい. 答えは$ dp_{0, 0}の値となり, 正ならば高橋くん, $ 0ならば引き分け, 負ならば青木くんがそれぞれ答えとなる.