ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

Educational DP Contest / DP まとめコンテスト L - Deque

問題
提出コード

解法

区間DPです。
dp[i][j] = [i,j]区間だけ数列が存在する場合についての、お互いが最善手を尽くした際のX-Yの値
とします。答えはdp[1][N]となります。
メモ化DPにするとやりやすいです。
初期値は、dp[i][i] = a_{i} or -a_{i}です。
Nが奇数ならそのまま、偶数なら-1倍します。
あとは、以下のように遷移を行えばよいです。現在見ているの区間の幅によって場合分けをします。

  • j-i+1の偶奇とNの偶奇が一致した場合
    dp[i][j] = max(a_{i}+dp[i+1][j],a_{j}+dp[i][j-1])

  • j-i+1の偶奇とNの偶奇が一致しなかった場合
    dp[i][j] = min(dp[i+1][j] -a_{i},dp[i][j-1] - a_{j})

となります。あとはこれをもとに遷移をすれば解くことができます。

感想

2人がゲームをするような問題が例によってすごく苦手だったので、最初に見た時はうわぁ…ってなったのですが、解法がDPとわかっていたので割とすんなり解くことができました。
制約を見たときに、N^{2}が間に合いそう、ってなったので、じゃぁ区間DPがいけそう、となりました。あとは、1回のターンでできる行動が2通りしかないので、その遷移について考えるだけで解けるな、という感じです。
この手の問題の一番厄介な部分が、偶奇による場合分けや添え字なので、そこに時間を費やしてしまったので少し解くのが遅くなってしまった気がします。ここをささっとできるようになりたいですね…