概要

カードが一列に並んでおり、先手の高橋君と後手の青木君が交互に左端か右端のカードを取っていくゲームで、両者が最適に行動したときの得点差（高橋の合計－青木の合計）を求める問題です。

考察

この問題は「二人零和有限確定完全情報ゲーム」の一種で、区間DP（動的計画法）が有効です。素朴な再帰的な探索では状態数が \(O(2^N)\) となり、\(N=3000\) では計算が不可能です。代わりに、区間 \([l, r]\) における最適な得点差をメモ化しながら計算するDPを考えます。

重要な観察は、現在のターンがどちらのプレイヤーかによって行動が変わることです。ターン数（残りカード数）から現在のプレイヤーがわかるため、DPの状態を区間 \([l, r]\) とし、その区間でこれからプレイするプレイヤーが最適に行動したときの得点差（高橋－青木）を計算します。

アルゴリズム

二次元配列 dp[l][r] を定義し、区間 \([l, r]\) のカードが残っているときの、これからのプレイで得られる得点差（高橋－青木）とします。

• 残りカード数が \(length = r-l+1\) のとき、ターン数は \(n - length\) 回経過しており、これが偶数なら高橋君のターン、奇数なら青木君のターンです。
• 高橋君のターン（\((n - length)\) % 2 == 0）では、自分の得点を最大化するように行動します。左端を取った場合の得点差は \(V[l] + dp[l+1][r]\)、右端を取った場合の得点差は \(V[r] + dp[l][r-1]\) なので、この最大値を選びます。
• 青木君のターン（\((n - length)\) % 2 == 1）では、得点差（高橋－青木）を最小化（＝自分の得点を最大化）するように行動します。左端を取ると得点差は \(-V[l] + dp[l+1][r]\)（高橋の得点から青木の得点 \(V[l]\) を引く）、右端を取ると \(-V[r] + dp[l][r-1]\) なので、この最小値を選びます。

区間の長さが小さい方から順に計算していき、最終的に dp[0][n-1] が全体の得点差となります。

計算量

• 時間計算量: \(O(N^2)\)
  • 状態数が \(O(N^2)\) で、各状態の計算が定数時間で行われるため。
• 空間計算量: \(O(N^2)\)
  • DPテーブルが \(N \times N\) の二次元配列のため。

実装のポイント

• 区間の長さ（length）を1から \(N\) まで順に増やしながらループします。

• 各長さについて、左端 l を動かし、対応する右端 r = l + length - 1 を計算します。

• ターンの判別は (n - length) % 2 == 0 で行い、高橋君と青木君で処理を分けます。

• 区間の長さが1のときは基本ケースとして別扱いします。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    V = list(map(int, data[1:1+n]))
    
    dp = [[0] * n for _ in range(n)]
    
    for length in range(1, n+1):
        for l in range(0, n - length + 1):
            r = l + length - 1
            if (n - length) % 2 == 0:
                if length == 1:
                    dp[l][r] = V[l]
                else:
                    left_choice = V[l] + dp[l+1][r]
                    right_choice = V[r] + dp[l][r-1]
                    dp[l][r] = max(left_choice, right_choice)
            else:
                if length == 1:
                    dp[l][r] = -V[l]
                else:
                    left_choice = -V[l] + dp[l+1][r]
                    right_choice = -V[r] + dp[l][r-1]
                    dp[l][r] = min(left_choice, right_choice)
                    
    print(dp[0][n-1])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。