概要

左右端から 1 枚ずつ取り合う 2 人零和ゲームとして捉え、区間 DP で「先手の得点 − 後手の得点」の最大値を求めます。

考察

このゲームは「自分の得点を最大化する」ことと同時に「相手に取らせたくないカードを残す」ことが絡みます。両者が最適に動くため、単純に「大きい方を取る」などの貪欲法は成立しません（次手以降で相手に有利なカードを渡してしまうことがあるため）。

また、各手で左右どちらを取るかの選択があり、素朴に全探索すると分岐が \(2^N\) になってしまい、\(N \le 3000\) では到底間に合いません。

重要な気づきは、このゲームが 零和（先手の得点 − 後手の得点）を最大化する問題として書けることです。
「今手番の人が、残っている区間から最適にプレイしたときに得られる差（自分 − 相手）」を DP で持つと、次の手番は相手に移るので差が反転する形になり、きれいな漸化式が作れます。

アルゴリズム

カード列を \(V_0, V_1, \dots, V_{N-1}\) とします（0-index）。

状態定義

区間 \([l, r]\)（両端含む）のカードが残っていて、今手番のプレイヤーが最適に動くときの 「（今手番の得点合計）−（相手の得点合計）」の最大値を

\[ dp[l][r] \]

と定義します。

遷移

今手番は左端 \(V_l\) を取るか、右端 \(V_r\) を取るかを選べます。

• 左端を取ると、次は相手が区間 \([l+1, r]\) で「相手 − 自分」の差を最大化します。その値が \(dp[l+1][r]\) なので、今手番視点の差は

\[ V_l - dp[l+1][r] \]

• 右端を取る場合も同様に

\[ V_r - dp[l][r-1] \]

よって漸化式は

\[ dp[l][r] = \max\bigl(V_l - dp[l+1][r],\; V_r - dp[l][r-1]\bigr) \]

初期値

区間長 1 のときはその 1 枚を取って終了なので

\[ dp[l][l] = V_l \]

答え

全区間 \([0, N-1]\) から先手（高橋君）が始めるので、求める値は

\[ dp[0][N-1] \]

1 次元 DP への圧縮（提出コードの形）

2 次元だと \(O(N^2)\) メモリになりますが、遷移で必要なのは「長さが 1 小さい区間」の値だけです。
そこで「現在の区間長における \(dp[l][r]\) を \(dp[l]\) に持つ」ようにして、

• ループで区間長 length を 2 から N まで伸ばす
• dp[l+1] はまだ更新前なので \(dp[l+1][r]\) を表す
• dp[l] は更新前なので \(dp[l][r-1]\) を表す

という対応関係で更新します（コード中の left = v[l] - dp[l+1], right = v[r] - dp[l]）。

計算量

• 時間計算量: \(O(N^2)\)（全ての区間 \([l,r]\) を 1 回ずつ計算）
• 空間計算量: \(O(N)\)（1 次元 DP 配列のみ）

実装のポイント

• 値が \(-10^9\) まであり得ますが、漸化式はそのまま正しく動きます（「差」で管理しているため）。

• 1 次元 DP 圧縮では更新順が重要です。l を小さい方から増やして更新すると、dp[l+1] が「更新前（=前の長さ）」のまま参照できて正しく計算できます。

• \(N=3000\) だと入出力もそれなりに大きいので、sys.stdin.buffer.read() でまとめて読む実装が安全です。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = data[1:1+n]

    dp = v[:]  # dp[l] = best (current player - other) for subarray [l..r] with current length
    for length in range(2, n + 1):
        end = n - length
        for l in range(end + 1):
            r = l + length - 1
            left = v[l] - dp[l + 1]
            right = v[r] - dp[l]
            dp[l] = left if left > right else right

    print(dp[0])

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。