概要

\(N\) 枚のカードが一列に並んでおり、二人のプレイヤーが交互に左端か右端からカードを取っていくゲームです。両者が最適に行動したときの各プレイヤーの得点を、区間DPを用いて求めます。

考察

重要な気づき

このゲームでは、どの時点でも「残っているカードは元の列の連続した部分列（区間）」になります。なぜなら、左端か右端しか取れないため、常に両端から削られていくだけだからです。

例えば \(A = [3, 1, -2, 5]\) のとき、高橋君が左端の \(3\) を取ると残りは \([1, -2, 5]\)、右端の \(5\) を取ると残りは \([3, 1, -2]\) となり、いずれも連続した区間です。

素朴なアプローチの問題

全ての選択パターンを探索すると、各手番で2通りの選択があり \(N\) 回の手番があるため \(O(2^N)\) となりTLEします。

解決の鍵：区間DP

残りのカードは常に区間 \([l, r]\) で表せるため、状態数は \(O(N^2)\) しかありません。ここで、現在の手番のプレイヤーから見た「自分の得点 − 相手の得点」の最大値 を \(dp[l][r]\) として定義するのがポイントです。

この定義なら、手番が高橋君でも青木君でも同じ遷移式が使えます。現在の手番のプレイヤーは自分と相手の得点差を最大化したいので：

\[dp[l][r] = \max(A[l] - dp[l+1][r],\; A[r] - dp[l][r-1])\]

• \(A[l] - dp[l+1][r]\)：左端を取って \(A[l]\) を得る。残りの区間 \([l+1, r]\) では相手が手番となり、相手視点の得点差が \(dp[l+1][r]\) なので、自分視点では \(-dp[l+1][r]\) となる。
• \(A[r] - dp[l][r-1]\)：右端を取る場合も同様。

アルゴリズム

1. DP テーブルの初期化: カード1枚の区間 \(dp[i][i] = A[i]\)（取るしかない）。
2. 区間の長さが短い方から長い方へ埋める: 長さ \(2, 3, \ldots, N\) の順に、各区間 \([l, r]\) について上記の遷移式で \(dp[l][r]\) を計算する。
3. 最終結果の復元: \(dp[0][N-1]\) は高橋君視点の「高橋の得点 − 青木の得点」です。カードの合計を \(S = \sum A_i\) とすると：
   • 高橋の得点 \(+\) 青木の得点 \(= S\)
   • 高橋の得点 \(-\) 青木の得点 \(= dp[0][N-1]\)

これを連立方程式として解くと： $\(\text{高橋の得点} = \frac{S + dp[0][N-1]}{2}, \quad \text{青木の得点} = \frac{S - dp[0][N-1]}{2}\)$

計算量

• 時間計算量: \(O(N^2)\) — 区間の数が \(O(N^2)\) で、各区間の遷移は \(O(1)\)
• 空間計算量: \(O(N^2)\) — DPテーブルのサイズ

実装のポイント

• DPの遷移で「\(-dp[l+1][r]\)」と符号を反転させる点が重要です。手番が変わると「自分」と「相手」が入れ替わるため、得点差の符号が逆転します。

• 区間DPでは短い区間から長い区間への順に計算する必要があります（長さ \(1 \to 2 \to \cdots \to N\)）。

• 全ての \(A_i\) が整数なので \(S + dp[0][N-1]\) と \(S - dp[0][N-1]\) は必ず偶数になり、整数除算で正しく求まります（高橋と青木は合わせてちょうど \(N\) 枚取り、\(N\) が奇数なら差も奇数だが合計との和・差は偶数になる）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[l][r] = the value of (current player's score - opponent's score)
    # for the subarray A[l..r] when it's the current player's turn
    # Base case: dp[i][i] = A[i] (take the only card)
    
    # dp[l][r] = max(A[l] - dp[l+1][r], A[r] - dp[l][r-1])
    
    dp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        dp[i][i] = A[i]
    
    for length in range(2, N + 1):
        for l in range(N - length + 1):
            r = l + length - 1
            take_left = A[l] - dp[l + 1][r]
            take_right = A[r] - dp[l][r - 1]
            dp[l][r] = max(take_left, take_right)
    
    # dp[0][N-1] = takahashi_score - aoki_score
    # takahashi_score + aoki_score = sum(A)
    total = sum(A)
    diff = dp[0][N - 1]
    
    takahashi = (total + diff) // 2
    aoki = (total - diff) // 2
    
    print(takahashi, aoki)

main()

---

この解説は claude4.6opus-thinking によって生成されました。