概要

テーブルに一列に並んだ \(N\) 枚のカードの左端か右端を交互に取り合うゲームで、両者が最適に行動したときの得点差を求める、典型的な区間DPの問題です。

考察

重要な気づき

このゲームでは、毎ターン「左端」か「右端」しか取れないため、どの時点でもテーブルに残っているカードは 元の列の連続部分列（区間） になっています。これが区間DPを適用できる大きなポイントです。

素朴なアプローチの問題点

各ターンで左端・右端の2択があるため、全探索すると分岐が \(2^N\) 通りとなり、\(N \leq 3000\) では到底間に合いません。

解決の方針：ゲーム理論的な区間DP

残っているカードの区間 \(V[i..j]\) に対して、「今手番のプレイヤーの得点 − 相手の得点」を \(dp[i][j]\) と定義します。

手番のプレイヤーが左端 \(V[i]\) を取ると、次の相手のターンでは区間 \(V[i+1..j]\) が残ります。相手にとっての「自分−相手」の値は \(dp[i+1][j]\) なので、今の手番のプレイヤーから見ると差は \(V[i] - dp[i+1][j]\) になります。右端 \(V[j]\) を取る場合も同様に \(V[j] - dp[i][j-1]\) です。

ここで 符号が反転する のがポイントです。\(dp[i+1][j]\) は「次の手番のプレイヤー（＝相手）の得点 − 自分の得点」なので、自分から見た差を計算するにはマイナスをつけます。

具体例

\(V = [4, 1, 3]\) の場合を考えます。

• \(dp[0][0] = 4,\ dp[1][1] = 1,\ dp[2][2] = 3\)（カード1枚なら取るだけ）
• \(dp[1][2] = \max(V[1] - dp[2][2],\ V[2] - dp[1][1]) = \max(1 - 3,\ 3 - 1) = 2\)
• \(dp[0][1] = \max(V[0] - dp[1][1],\ V[1] - dp[0][0]) = \max(4 - 1,\ 1 - 4) = 3\)
• \(dp[0][2] = \max(V[0] - dp[1][2],\ V[2] - dp[0][1]) = \max(4 - 2,\ 3 - 3) = 2\)

よって高橋君の得点 − 青木君の得点 \(= 2\) です。

アルゴリズム

1. 状態定義: \(dp[i][j]\) = 区間 \(V[i..j]\) が残っているとき、手番プレイヤーの得点 − 相手の得点（最適プレイ時）
2. 初期条件: \(dp[i][i] = V[i]\)（カード1枚なら取るしかない）
3. 遷移: 区間の長さが短い方から順に計算する

\[dp[i][j] = \max(V[i] - dp[i+1][j],\ V[j] - dp[i][j-1])\]

1. 答え: 最初のターンは高橋君の手番なので、\(dp[0][N-1]\) がそのまま「高橋君の得点 − 青木君の得点」

計算量

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

実装のポイント

• 区間DPは区間の長さが短い方から順に計算する必要があります。長さ1 → 長さ2 → … → 長さ \(N\) の順にループします。

• 遷移式の \(-dp[i+1][j]\) の マイナス符号 を忘れないこと。手番が入れ替わるたびに「自分と相手」が反転するため、相手の最適値を引く形になります。

• \(V_i\) が負の値を取りうるため、データ型のオーバーフローに注意が必要です（Python では整数のオーバーフローはありません）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    V = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[i][j] = the value of (current player's score - opponent's score)
    # for the subarray V[i..j]
    # When it's a player's turn, they pick left or right to maximize their own total.
    # dp[i][j] = max(V[i] - dp[i+1][j], V[j] - dp[i][j-1])
    
    dp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        dp[i][i] = V[i]
    
    for length in range(2, N + 1):
        for i in range(N - length + 1):
            j = i + length - 1
            dp[i][j] = max(V[i] - dp[i + 1][j], V[j] - dp[i][j - 1])
    
    print(dp[0][N - 1])

main()

---

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