概要

\(N\) 枚のカードが並んだ列から、二人が交互に左端か右端を取り除き、最後に残る1枚のスコアを求めるミニマックスゲームの問題です。区間DPで解けます。

考察

重要な気づき

1. ゲームの状態は「残っている連続区間」で決まる: 左端か右端しか取り除けないため、どの段階でも残っているカードは元の配列の連続部分列 \(A[l..r]\) になります。

2. 誰の手番かは区間の長さから分かる: 最初は \(N\) 枚あり、\(N\) 枚のときは高橋君の番です。カードが1枚取り除かれるごとに手番が交代します。つまり、今まで取り除かれた枚数 \(N - (r - l + 1)\) が偶数なら高橋君の番、奇数なら青木君の番です。

3. 区間DPが適用できる: 残りの区間 \([l, r]\) が状態であり、そこから左端を取る（\([l+1, r]\) に遷移）か右端を取る（\([l, r-1]\) に遷移）かの2択を、手番の人が最適に選びます。

素朴なアプローチとの比較

全探索では各手番で2通りの選択があり、操作は \(N-1\) 回なので \(O(2^{N-1})\) かかります。\(N = 3000\) ではとても間に合いません。しかし、状態を区間 \([l, r]\) で管理すれば状態数が \(O(N^2)\) に抑えられ、効率的に解けます。

アルゴリズム

区間DP を用います。

• 状態: \(dp[l][r]\) = カードが \(A[l], A[l+1], \ldots, A[r]\) だけ残っているときの、最適プレイでの最終スコア
• 基底: 区間の長さが1のとき、\(dp[i][i] = A[i]\)（最後の1枚がそのままスコア）
• 遷移: 区間の長さが2以上のとき
  • 取り除かれた枚数 \(\text{removed} = N - (r - l + 1)\)
  • \(\text{removed}\) が偶数 → 高橋君の番 → \(dp[l][r] = \max(dp[l+1][r],\ dp[l][r-1])\)
  • \(\text{removed}\) が奇数 → 青木君の番 → \(dp[l][r] = \min(dp[l+1][r],\ dp[l][r-1])\)

短い区間から順に計算していき、最終的に \(dp[0][N-1]\) が答えです。

具体例

\(A = [3, 1, 5]\) (\(N=3\)) の場合：

• \(dp[0][0]=3,\ dp[1][1]=1,\ dp[2][2]=5\)
• 長さ2: removed=1（青木の番）
  • \(dp[0][1] = \min(dp[1][1], dp[0][0]) = \min(1, 3) = 1\)
  • \(dp[1][2] = \min(dp[2][2], dp[1][1]) = \min(5, 1) = 1\)
• 長さ3: removed=0（高橋の番）
  • \(dp[0][2] = \max(dp[1][2], dp[0][1]) = \max(1, 1) = 1\)

答えは \(1\) です。

計算量

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

実装のポイント

• 区間の長さが短い方から順に計算する（ボトムアップDP）ことで、遷移先が必ず計算済みになります。

• 手番の判定は「取り除かれた枚数 = \(N\) - 現在の区間の長さ」の偶奇で行います。\(N\) が奇数か偶数かによって各長さでの手番が変わるため、固定的に「奇数長なら〇〇の番」とはならない点に注意してください。

• \(N = 1\) の場合は操作が行われないため、そのまま \(A[0]\) を出力します。

  ソースコード

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = list(map(int, input_data[1:N+1]))
    
    if N == 1:
        print(A[0])
        return
    
    # dp[l][r] = the score when the remaining cards are A[l..r]
    # The number of cards removed so far is N - (r - l + 1)
    # If N - (r-l+1) is even, it's Takahashi's turn (he wants max)
    # If N - (r-l+1) is odd, it's Aoki's turn (he wants min)
    # Base case: when r - l + 1 == 1, dp[l][r] = A[l]
    
    # We'll iterate by length of interval
    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
            removed = N - length
            # removed cards so far, next person to act:
            # removed == 0 means Takahashi acts (wants to maximize)
            if removed % 2 == 0:
                # Takahashi's turn: he removes left or right to maximize final score
                dp[l][r] = max(dp[l+1][r], dp[l][r-1])
            else:
                # Aoki's turn: he removes left or right to minimize final score
                dp[l][r] = min(dp[l+1][r], dp[l][r-1])
    
    print(dp[0][N-1])

solve()

---

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