問題概要

問題文はこちらを参照してください。

解法

「ゲームでお互いが最善を尽くしたとき」という問題は、どちらか片方のプレイヤー側から見た場合の状態を考えるとうまくいくと思います。また、DPは実際に求めたいものを設定するのが良いと言われています。ということで、ある状態でのその時以降に先手が取れるものの価値の合計を考えます。

先手が取る番の時は、左右の山どちらかの物を取った後の状態から得られる価値の合計がわかっていれば、今から取るものと取った後の状態から得られる価値の和が大きくなるように取ります。

後手が取る番の時は、その状態で先手が得られる価値の合計は後手が取った後の状態から得られる価値の合計になります(後手が取っても先手の合計は増えないので)。従って、後手が最善を尽くすということは、先手にとっては最悪なので、取った後に先手が得られる価値が少なくなるように取ります。

漸化式の定義: $$\begin{eqnarray} dp[i][j] & = & \begin{cases} \max\{dp[i-1][j]+a_{A+1-i},\ dp[i][j-1]+b_{B+1-j}\} & (先手の番) \\ \min\{dp[i-1][j],\ dp[i][j-1]\} & (後手の番) \end{cases}\\ dp[0][j] & = & \begin{cases} dp[0][j-1]+b_{B+1-j} & (先手の番) \\ dp[0][j-1] & (後手の番) \end{cases}\\ dp[i][0] & = & \begin{cases} dp[i-1][0]+a_{A+1-i} & (先手の番) \\ dp[i-1][0] & (後手の番) \end{cases} \end{eqnarray}$$

$dp[i][j]$:左の山に$i$個、右の山に$j$個のものが残っている状態で、その状態から終了までに先手が得られる価値の合計 $(0\le i \le A,\ 0\le j \le B)$

$a_k$:左の山の上から$k$番目の物の価値$(1\le k \le A)$

$b_k$:右の山の上から$k$番目の物の価値$(1\le k \le B)$

初期値:$dp[0][0]=0$

求める解:$dp[A][B]$

先手の番か後手の番かは、これまでに取った物の数($A+B-(i+j)$)が偶数か奇数かで判断します。

考察

お互いに最善な戦略をとったときって、漸化式をどちらの目線で定義したかを意識しないと、何が最善なのかがこんがらがることが多いです。

ちなみに、$i,\ j$を左の山から$i$個、右の山から$j$個取った状態という風に、逆のインデックスのほうがわかりやすかったりするのでしょうか。どうも他の方の解説を見ると、逆になっていることが多い気がします。