概要

高橋君と青木君が交互にカードの両端からカードを取り合い、最終的に高橋君の得点から青木君の得点を引いた値を最大化する問題です。

考察

このゲームでは、各プレイヤーが「自分の得点を最大化」ではなく、「自分と相手の得点差を最大化」するように動く必要があります。つまり、単純に貪欲に大きい数字を選ぶだけでは最適ではありません。

例えば、カードが [1, 2, 100, 3] のように並んでいる場合、左端の 1 を取るよりも右端の 3 を取ったほうが良さそうですが、それによって相手が 100 を取れるようになってしまうため、結果として得点差が悪化する可能性があります。

このような「お互いが最適に動く」という状況では、動的計画法（DP）が有効です。特に、区間に関するDP（区間DP）が適用できます。

素朴な全探索では、各ターンで左右どちらを選ぶかの選択肢があり、最大で \(2^N\) の選び方があるため、TLEになります。制約 \(N \leq 3000\) なので、計算量を抑える必要があります。

そこで、区間DPを用いて、区間 [i, j] の範囲のカードが残っているときに「現在の手番の人が最終的に得られる得点差」を前計算しておきます。

アルゴリズム

区間DPを用います。以下のようにDPテーブルを定義します：

\(DP[i][j]\) := 残っているカードが \(i\) 番目から \(j\) 番目まであるとき、現在の手番の人が最終的な得点差（現在の手番の人の得点 − 相手の得点）を最大化する値

初期条件： - カードが1枚だけ残っている場合、そのカードを取るのが最適なので、
$\(DP[i][i] = V[i]\)$

遷移： - カードが複数枚あるとき、現在の手番の人は左端または右端のどちらかを選ぶことができます。 - 左端を選ぶ場合： - 得点 \(V[i]\) を得て、次は区間 \([i+1, j]\) で相手の手番になるので、相手が最適に動いたときの得点差 \(DP[i+1][j]\) を引く必要がある。 - 得点差は \(V[i] - DP[i+1][j]\) - 右端を選ぶ場合も同様： - 得点差は \(V[j] - DP[i][j-1]\)

したがって、遷移式は以下の通り： $\( DP[i][j] = \max(V[i] - DP[i+1][j],\ V[j] - DP[i][j-1]) \)$

最後に求めたいのは、最初の区間 \([0, N-1]\) における高橋君の得点差なので、 $\( DP[0][N-1] \)$ を出力すればよいです。

例

入力例：

4
1 2 100 3

DPテーブルの更新過程において、最終的に \(DP[0][3]\) が高橋君の得点差として求められます。

計算量

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

各区間に対して1回ずつ計算を行うため、時間計算量は二次オーダーとなります。空間も同じく二次のテーブルを使います。

実装のポイント

• DPテーブルの更新順序に注意すること。短い区間から長い区間へと更新していく必要があります。

• 初期化はカードが1枚のときに行い、その後長さ2以上の区間を処理する。

• 引くときに相手の最適値を引いている点がポイント（得点差を考えているため）。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    V = list(map(int, data[1:N+1]))
    
    # DP[i][j] := 残っているカードが i 番目から j 番目までのとき、
    # その時の手番の人が最終的な得点差（現在の手番の人 - 相手）を最大化したときの値
    DP = [[0]*N for _ in range(N)]
    
    # 初期化: 残るカードが1枚のとき
    for i in range(N):
        DP[i][i] = V[i]
    
    # 区間DP: len が 2 以上の場合
    for length in range(2, N+1):       # length はカードの枚数
        for i in range(N - length + 1):
            j = i + length - 1
            # 左端を取る場合：V[i] を得て、次の相手の最適解を引く
            left_choice = V[i] - DP[i+1][j]
            # 右端を取る場合：V[j] を得て、次の相手の最適解を引く
            right_choice = V[j] - DP[i][j-1]
            DP[i][j] = max(left_choice, right_choice)
    
    print(DP[0][N-1])

if __name__ == "__main__":
    main()

---

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