DPまとめコンテスト/L - Deque - 競技プログラミング用 知識集積所【7/18更新】

---

問題

DP-L

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• 二人零和有限確定完全情報ゲーム（未作成）
• バックトレース

考え方

値というよりは範囲を広げていく動的計画法、通称範囲DP。
といっても、そこまで特殊な考えなわけではない。
左端と右端の位置を使った2次元の動的計画法で、初期値をいれる場所と継承の方向が少し独特なだけ。

まず、問題を少しわかりやすく言い換える。
太郎君はX-Yを最大化しようとし、次郎君は最小化する、とあるが、これはわかりにくい。
太郎君はX-Yを最大化しようとし、次郎君はY-Xを最大化しようとする、の方がいい。

なぜなら、その変更によって、単純な二人零和有限確定完全情報ゲーム（未作成）になるから。
自分が行動した全パターンについて「自分の行動で得る点-その後の最善手での結果」を計算して、それの最大値を求めるだけでよくなる。
また、終了パターンがある程度限られることもあり、バックトレースで考えることになる。

例えば入力例1の場合。

最初に、次のように初期化する。
残り1つの場合、それを取るしか選択肢がないので、その得点がそのまま最大値。

左端＼右端	10	80	90	30
10	10	-	-	-
80	-	80	-	-
90	-	-	90	-
30	-	-	-	30

次に黄色マスを考える。
このマスは{90,30}という状態での先手の得点予測である。

左端から取る場合、まず自分に90点入る。
その後の展開は、下のマスを見れば、相手の方が30点多くなる展開が予測できる。
つまり、左端から取った場合の得点予測は30点となる。

同様に、右端から取る場合、自分に30点、その後相手が90点多く取るので、得点予測は-60点。
よって、多い方を考えて、ここの得点予測は60点となる。

こうして、下段から順に、左から埋めていくことができる。

左端＼右端	10	80	90	30
10	10	70	20	10
80	-	80	10	20
90	-	-	90	60
30	-	-	-	30

右上の10が答えである。
左下部分はメモリが無駄になるので、実務だったらちょっと考えないといけないが、競プロなら関係ない。

あとは、これをコードにすればよい。

解答例

解答例

注意点

別解