概要

この問題は、2人のプレイヤーが列の両端からカードを取り合うゲームにおいて、双方が自身の得点を最大化するように最適に行動したときの「（先手の合計点）-（後手の合計点）」を求める問題です。

考察

このゲームは「零和（ゼロサム）ゲーム」に近い性質を持っており、一方の得点が増えることは、もう一方の得点が相対的に減ることを意味します。このようなゲームでは、動的計画法（DP）を用いて、小さい部分問題から解いていく手法が有効です。

重要な気づき

1. 状態の定義: ゲームの状況は「まだ残っているカードの範囲 \([i, j]\)」だけで決まります。
2. 目的関数: 手番のプレイヤーが最大化したいのは「（自分の得点）-（相手の得点）」です。
   • 範囲 \([i, j]\) において、今のプレイヤーが左端 \(V_i\) を取った場合、その後の差分は \(V_i - (\text{範囲 } [i+1, j] \text{ における相手から見た最大差分})\) となります。
   • 同様に、右端 \(V_j\) を取った場合は \(V_j - (\text{範囲 } [i, j-1] \text{ における相手から見た最大差分})\) となります。
3. 最適戦略: プレイヤーは上記の2つの選択肢のうち、値が大きくなる方を選びます。

単純な再帰（全探索）では、カードの取り方が \(2^N\) 通りあり、\(N=3000\) では到底間に合いません。しかし、カードの範囲 \([i, j]\) の組み合わせは \(N^2\) 通りしかないため、一度計算した結果を再利用するDPを用いることで、効率的に解くことができます。

アルゴリズム

動的計画法

以下のDPテーブルを定義します。 - \(dp[i][j]\) : カードの範囲が \(V_i\) から \(V_j\) まで残っているとき、その時の手番のプレイヤーが達成できる「（自分の合計点）-（相手の合計点）」の最大値。

遷移式: - カードが1枚のとき（ベースケース）: \(dp[i][i] = V_i\) - カードが複数枚（長さ \(L = j - i + 1\)）のとき: \(dp[i][j] = \max(V_i - dp[i+1][j], \quad V_j - dp[i][j-1])\)

この計算を、カードの長さ \(L\) が \(1\) から \(N\) まで順に計算していきます。最終的な答えは \(dp[0][N-1]\) となります。

計算量

• 時間計算量: \(O(N^2)\) カードの範囲の組み合わせ（状態数）が \(N(N+1)/2\) 個あり、各遷移を \(O(1)\) で計算できるため、\(N=3000\) のとき約 \(4.5 \times 10^6\) 回の計算となり、実行時間制限内に十分収まります。
• 空間計算量: \(O(N)\) 愚直に実装すると \(O(N^2)\) のメモリが必要ですが、長さ \(L\) の計算には長さ \(L-1\) の結果しか使わないため、1次元配列を使い回すことで \(O(N)\) に抑えることができます。

実装のポイント

• メモリの節約: \(N=3000\) の場合、\(3000 \times 3000\) の2次元配列を確保するとメモリを多く消費します。提供されたコードのように、1次元配列 dp を更新していく形式にすることでメモリ使用量を節約しています。

• 実行速度の最適化: Pythonでは組み込み関数の max() を呼び出すよりも、if 文による比較の方が高速に動作する場合があります。特に \(O(N^2)\) の内側ループのような実行回数が多い箇所では、この差が実行時間に影響します。

• 高速な入出力: sys.stdin.read().split() を使うことで、大量の入力を一括で読み込み、処理を高速化しています。

  ソースコード

import sys

def main():
    # Read all input at once for efficiency. sys.stdin.read().split() 
    # splits the input into a list of strings by whitespace.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N is the number of cards.
    # V is the list of integers written on the cards.
    n = int(input_data[0])
    v = list(map(int, input_data[1:]))
    
    # We use a Dynamic Programming approach to solve this minimax game.
    # Let f(i, j) be the maximum value of (current player's sum - opponent's sum)
    # for the cards in the range [i, j].
    # The base case is when only one card is left: f(i, i) = V[i].
    # For a range [i, j], the current player can pick either V[i] or V[j].
    # If they pick V[i], the difference becomes V[i] - f(i+1, j).
    # If they pick V[j], the difference becomes V[j] - f(i, j-1).
    # Each player acts optimally to maximize this difference.
    
    # dp[i] will store the result for a subarray of the current 'length'
    # starting at index i. This allows us to use O(N) space.
    # Initialize the DP table for length 1.
    dp = list(v)
    
    # Iterate through possible lengths of subarrays from 2 up to N.
    for length in range(2, n + 1):
        # offset represents the distance from the left index i to the right index j.
        offset = length - 1
        
        # Calculate the DP value for each subarray of the current length.
        # We update the dp array in-place. dp[i] for 'length' is calculated 
        # using dp[i] and dp[i+1] from 'length - 1'.
        for i in range(n - length + 1):
            # Option 1: Pick the leftmost card v[i].
            # Option 2: Pick the rightmost card v[i + offset].
            
            # Use a simple if-else instead of the max() function for a slight performance gain in Python.
            opt_left = v[i] - dp[i + 1]
            opt_right = v[i + offset] - dp[i]
            
            if opt_left > opt_right:
                dp[i] = opt_left
            else:
                dp[i] = opt_right
                
    # The final answer is the maximum difference for the full array (length N) starting at index 0.
    print(dp[0])

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-thinking によって生成されました。