Educational DP Contest / DP まとめコンテスト L - Deque
解法
区間DPです。
の区間だけ数列が存在する場合についての、お互いが最善手を尽くした際のの値
とします。答えはとなります。
メモ化DPにするとやりやすいです。
初期値は、です。
が奇数ならそのまま、偶数なら-1倍します。
あとは、以下のように遷移を行えばよいです。現在見ているの区間の幅によって場合分けをします。
の偶奇との偶奇が一致した場合
の偶奇との偶奇が一致しなかった場合
となります。あとはこれをもとに遷移をすれば解くことができます。
感想
2人がゲームをするような問題が例によってすごく苦手だったので、最初に見た時はうわぁ…ってなったのですが、解法がDPとわかっていたので割とすんなり解くことができました。
制約を見たときに、が間に合いそう、ってなったので、じゃぁ区間DPがいけそう、となりました。あとは、1回のターンでできる行動が2通りしかないので、その遷移について考えるだけで解けるな、という感じです。
この手の問題の一番厄介な部分が、偶奇による場合分けや添え字なので、そこに時間を費やしてしまったので少し解くのが遅くなってしまった気がします。ここをささっとできるようになりたいですね…