L – Deque 解説 (Educational DP Contest / DP まとめコンテスト)

2020年3月10日AtCoderDP, 競プロ, ゲーム, 二人零和有限確定完全情報ゲーム, 後退解析, 最大化, 最小化, 区間DP

問題へのリンク

問題概要

数列 \(a = a_1, a_2, \ldots, a_N \) がある。二人で以下の操作を交互に行う。

  • a の先頭要素または末尾要素を取り除く。 取り除いた要素を x とすると、操作を行った人は x 点を得る。

先手の得点を X, 後手の得点を Y とする時、先手は X-Y を最大化しようとし、後手は X-Yを最小化しようとする。
最終的な X-Y の値は何か?

制約

  • \(1 \leq N \leq 3000\)
  • \(1 \leq a_i \leq 10^9\)

考え方

問題K と同じくゲームに関する問題です。後退解析という考え方が使えます。

後退解析とは、「ゲームの終了状態から出発して、ゲームの開始状態まで逆方向に解析していくこと」です。

ゲームの終了状態(数列が全て取り除かれた時)から逆に考えて、ゲーム開始時点までの状態を探索していきます。

dp[ i ][ j ] := 区間 [ i, j ) 番目の数列から始めて最善手を取った時の、最終的な X-Y の値

遷移の方法としては、まずどちらの手番なのかを考える必要があります。実は残り個数 (j-i) の時は、今までに取った数は N -(j-i) になるので、

  • N – (j-i) が偶数のとき:先手の手番
  • N – (j-i) が奇数のとき:後手の手番

になることが分かります。先手の時は最終スコアが増加し、後手の時は最終スコアが減少するようにしなければなりません。

数列の取り方としては、

  • \(a_i\) を取る時
  • \(a_j\) を取る時

の2種類があり、この2つの場合を考えてやれば良いです。

初期化

  • dp[ i ][ i ] = 0

残り個数が 0個の時はどちらも得点が 0 なので、 X-Y も 0 になります。

更新

  • N – (j-i) が偶数のとき:先手の手番
    • dp[ i ][ j ] = max(dp[ i ][ j – 1 ] + A[ j – 1 ], dp[ i + 1 ][ j ] + A[ i ]);
  • N – (j-i) が奇数のとき:後手の手番
    • dp[ i ][ j ] = min(dp[ i ][ j – 1 ] – A[ j – 1 ], dp[ i + 1 ][ j ] – A[ i ]);

更新の順序には注意が必要です。既に更新が終わった部分を利用して、次の更新を行う必要があります。

メモ化再帰で実装したほうがやりやすいかもしれません。

C++での実装例

メモ化再帰

今回のように dp の更新を for 文で書きにくい場合は、メモ化再帰の方が実装しやすいです。

dp で更新

dp配列の対角線に並行に更新しました。