Typical DP Contest B - ゲーム - ツバサの備忘録

問題
 提出コード
いきなり難易度高くないですか…？

解法

左右それぞれの山に積まれている物の合計個数の偶奇によって、どちらのターンかは一意に決まります。
$A+B$ が偶数のとき、左右の合計が奇数であれば、次は後攻、偶数であれば先攻です。
$A+B$ が奇数の場合はこの逆になります。
さて、次のようなDPを考えていきます。

$dp[i][j] =$ 左の山の物の個数が $i$ 個、右が $j$ 個であったとき、ここからお互いが最適に動いた場合に得られる、すぬけ君が選んだ物の価値の合計

こうすることで、答えは $dp[A][B]$ を見ればいいことがわかります。
また、初期状態は、 $dp[0][0] = 0$ です。
さて、左右の山に積まれた物の個数の合計によってターンがどちらかが変わるので、左が $i$ 個、右が $j$ 個の山になっていた場合のそれぞれについて最適な行動を考えてみます。

左が $i$ 個、右が $j$ 個で先攻だったパターン
左から物をとると、その価値は $a_{A-i+1}$ であり、右からとった場合は、 $b_{B-j+1}$ です。
それ以降お互いが最適な行動をした場合のすぬけ君の合計価値は、前者のパターンが $dp[i-1][j]$ 、後者が $dp[i][j-1]$ であるので、この値と、このターンでとった物の価値を合計して、より良い方を選べばよいです。ということで、
$dp[i][j] = max(dp[i-1][j]+a_{A-i+1},dp[i][j-1]+b_{B-j+1})$
左が $i$ 個、右が $j$ 個で後攻だったパターン
このターンでは、左と右どちらを選んでもすぬけ君の合計価値自体は変化がないです。が、すめけ君は、すぬけ君の合計価値ができるだけ小さくなるように行動をするので、
$dp[i][j] = min(dp[i-1][j],dp[i][j-1])$
となります。

あとは、この遷移をもとにしてDPをしていきます。今の状態がどちらのターンなのかに気を配る必要があります。
そして、 $dp[A][B]$ を見れば、最終的な答えがわかります。