TDPC B - ゲーム
考え方
ABCでいうと、難しめD問題級。
最初に入力を反転するとコードが書きやすいので、説明も全て反転した状態に合わせて書く。
Aが残り $i$ 個、Bが残り $j$ 個の場合の得点を求めていく動的計画法で解けそう。
が、問題は値として何を持つか。
その状況での手番がすぬけくんかすめけくんかで、保持する値を変えるのは、複雑。
そこで、少し工夫する。
Aが残り $i$ 個、Bが残り $j$ 個の場合の「先手の点数 $-$ 後手の点数」を持つことにする。
すると、DP は以下のように遷移する。
$$
DP[i][j] =
\begin{cases}
0 & (i=0,\ j=0), \\
b_{j-1} - DP[i][j-1] & (i=0,\ j>0), \\
a_{i-1} - DP[i-1][j] & (i>0,\ j=0), \\
\max\left(b_{j-1} - DP[i][j-1], a_{i-1} - DP[i-1][j]\right) & (i>0,\ j>0).
\end{cases}
$$
こうすると、DPテーブルの右下の値が、最終的な「すぬけくんの点数 $-$ すめけくんの点数」となる。
よって、これに $a$ も $b$ も含めた全ての価値の合計を加えて $2$ で割ると答えになる。
また、一次元データでインライン（というかインプレース）で更新してもよい。
計算量は $O(AB)$。
入力例2での動作
入力を受け取る。
以下では、左の山の長さを n、右の山の長さを m とする。
n: 5
m: 5
a: {2, 4, 5, 4, 2}
b: {2, 8, 3, 4, 5}dp[i][j] を、A が $i$ 個、B が $j$ 個残っている状態の値とする。
値は「現在の手番の人の得点 $-$ 相手の得点」の最大値とする。
DP テーブルは次のようになる。
| A の残り個数＼B の残り個数 | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ |
|---|---|---|---|---|---|---|
| $0$ | 0 | 5 | -1 | 4 | 4 | -2 |
| $1$ | 2 | 3 | 3 | 0 | 8 | 4 |
| $2$ | 2 | 3 | 1 | 4 | 4 | 0 |
| $3$ | 3 | 2 | 4 | 1 | 7 | 5 |
| $4$ | 1 | 4 | 0 | 3 | 5 | -1 |
| $5$ | 1 | 4 | 2 | 1 | 7 | 3 |
例えば dp[1][1] では、a から取る場合と b から取る場合を比較する。
aから取る: 2 - 5 = -3
bから取る: 5 - 2 = 3よって dp[1][1] = 3 となる。
最終的に、すぬけ君の得点 $-$ すめけ君の得点は dp[5][5] = 3 である。
全ての価値の合計は $17+22=39$ なので、答えは $(3+39)/2=21$。
注意点
特になし。
別解
特になし。