概要

左右の端からカードを取り除いていき、最後に残ったカードの値を最大化（先手）・最小化（後手）するゲームの結果を求める問題。

考察

この問題では、二人が最適に動くという前提で、最終的にどのカードが残るか（すなわちスコアがいくつになるか）を求めます。

素朴な方法として、全探索でゲームの進行をシミュレートすることを考えますが、各ステップで左右どちらを選ぶかによって分岐が生じ、全体の探索空間が指数時間になってしまいます。そのため、効率的な解法が必要です。

重要な気づきは、「ゲームの途中状態は連続した区間で表せる」ことです。つまり、操作を重ねてもカードは常に連続した部分配列として残っています。例えば、左から3枚、右から2枚取られていれば、残っているのは中央の連続した区間です。

この性質を利用すると、「区間DP（動的計画法）」という手法が適用できます。具体的には、dp[l][r] を「残りが A[l] から A[r] の区間であるときに、最終的なスコアが何になるか」と定義します。

次に、遷移を考えます。現在の区間 [l, r] に対して、次の一手で左端 l または右端 r を取り除くことができます。どちらを選ぶかは、その時点でのプレイヤーの目的（スコアを最大化／最小化）に従って決まります。

さらに、誰のターンかを判断する必要があります。初期状態で \(N\) 枚あり、区間 [l, r] の長さが \(r-l+1\) なので、操作回数は \(N - (r - l + 1)\) です。これが偶数なら先手、奇数なら後手のターンです。

このようにして、小さい区間から順に dp[l][r] を埋めていけば、最終的に dp[0][N-1] が答えになります。

アルゴリズム

区間DP（動的計画法）を用いて、区間 [l, r] のスコアを再帰的に求めます。

ステップ

1. dp[l][r] を「区間 [l, r] が残っているときの最終スコア」と定義。
2. 初期条件：区間の長さが1（つまり \(l = r\)）のときは、そのカードの値がスコア：
   

   
   dp[i][i] = A[i]
   

3. 長さ2以上の区間については、区間の長さの短い順に計算：
   • 先手（操作回数が偶数）のターンなら、左か右を選んでスコアを最大化
   • 後手（操作回数が奇数）のターンなら、左か右を選んでスコアを最小化

遷移式は以下の通り：

• 先手のターン（スコア最大化）：
  $\( dp[l][r] = \max(dp[l+1][r],\ dp[l][r-1]) \)$

• 後手のターン（スコア最小化）：
  $\( dp[l][r] = \min(dp[l+1][r],\ dp[l][r-1]) \)$

最終的な答えは dp[0][N-1] です。

計算量

• 時間計算量: \(O(N^2)\)
• 空間計算量: \(O(N^2)\)

各区間 [l, r] を1回ずつ処理するので、時間計算量は \(O(N^2)\)。dpテーブルのサイズも \(N \times N\) なので、空間計算量も同様。

実装のポイント

• 区間の長さを2から順に増やすことで、必要な情報がすでに計算されていることを保証する。

• ターン数の計算：turn = N - (r - l + 1) が偶数なら先手、奇数なら後手。

• Pythonでは再帰ではなくループでDPを更新するのが安全かつ高速。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    A = list(map(int, data[1:N+1]))
    
    # dp[l][r] := 残りがA[l], A[l+1], ..., A[r]のときのスコア
    dp = [[0]*N for _ in range(N)]
    
    # 初期化: 残り1枚の場合はその値がスコア
    for i in range(N):
        dp[i][i] = A[i]
    
    # 区間DP: len=2以上について計算
    for length in range(2, N+1):       # 残り枚数
        for l in range(N - length + 1): # 左端
            r = l + length - 1          # 右端
            # 先手のターンならスコアを最大化、後手のターンなら最小化
            # ターン数 = N - (r - l + 1) → 先手は偶数、後手は奇数
            turn = N - (r - l + 1)
            if turn % 2 == 0:  # 先手のターン（スコア最大化）
                dp[l][r] = max(dp[l+1][r], dp[l][r-1])
            else:              # 後手のターン（スコア最小化）
                dp[l][r] = min(dp[l+1][r], dp[l][r-1])
    
    print(dp[0][N-1])

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。