概要

左右からカードを取り合い、最終的な得点差を最大化するゲームにおいて、両者が最適に行動したときの高橋君と青木君の得点を求めます。

考察

このゲームは「二人零和ゲーム」と呼ばれるタイプの問題であり、どちらのプレイヤーも「自分の得点 − 相手の得点」を最大化するように行動します。

素朴な方法として、全探索によってすべての取り方を試すことを考えますが、手番ごとに左右の選択があり、深さ \(N\) の探索が必要になるため、計算量は指数時間となり、\(N\) が最大 \(3000\) なので到底間に合いません。

また、貪欲法（例：毎回一番大きな数字を取る）も正しくありません。なぜなら、今すぐ少し得しても、後に相手に良いカードを残してしまう可能性があるからです。

そこで、「残っているカードの区間に対して、その区間で先手が得られる最大の得点差」を記録する動的計画法（区間DP）を用いるのが有効です。

区間 \([i, j]\) に対して、その区間での得点差の最適値を dp[i][j] と定義します。このとき、現在の手番のプレイヤーは左端 \(A[i]\) または右端 \(A[j]\) を取ることができ、その後は相手の手番になります。相手も最適に行動するので、自分は「取ったカードの得点 − 次の区間での相手の最適得点差」を最大化する必要があります。

例えば、区間 \([i, j]\) で左端を取る場合： $\( \text{得点差} = A[i] - dp[i+1][j] \)\( 右端を取る場合も同様に： \)\( \text{得点差} = A[j] - dp[i][j-1] \)$ このうち大きい方を選ぶのが最適です。

初期条件としては、カードが1枚だけ残っているとき（区間長が1）、そのカードの値そのものが得点差となります。

最後に、求めたのは「得点差」です。高橋君の得点を \(T\)、青木君の得点を \(A\) とすると、 - \(T - A = \text{dp}[0][N-1]\) - \(T + A = \sum A\)

これら2つの式から連立方程式を解くことで、 $\( T = \frac{\text{sum} + \text{diff}}{2}, \quad A = \frac{\text{sum} - \text{diff}}{2} \)$ として求められます。

アルゴリズム

区間DP（動的計画法）を用います。

• dp[i][j]: 残っているカードが \(i\) 番目から \(j\) 番目までの区間にあるとき、その区間で現在の手番の人が得られる最大の得点差
• 遷移: $\( dp[i][j] = \max(A[i] - dp[i+1][j],\ A[j] - dp[i][j-1]) \)$
• 初期条件: dp[i][i] = A[i]

区間の長さを短いものから順に埋めていきます（ボトムアップ方式）。

計算量

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

実装のポイント

• DPテーブルを2次元で確保し、区間の長さを2から順に埋めていく。

• 最終的に得点差と総和から個々の得点を求めるときに、整数除算 / ではなく // を使う（Pythonでは安全）。

• 入力を高速に読み込むために sys.stdin.read を使用している。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    A = 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] = A[i]
    
    # 区間DP：len = 2 から N まで
    for length in range(2, N+1):  # 部分列の長さ
        for i in range(N - length + 1):
            j = i + length - 1
            # 左端を取る場合と右端を取る場合のうち、
            # 得点差を最大化するように選ぶ
            take_left = A[i] - dp[i+1][j]
            take_right = A[j] - dp[i][j-1]
            dp[i][j] = max(take_left, take_right)
    
    # 高橋君の得点 - 青木君の得点 = dp[0][N-1]
    diff = dp[0][N-1]
    # 高橋君の得点 + 青木君の得点 = sum(A)
    total = sum(A)
    
    # 高橋君の得点 = (total + diff) // 2
    takahashi = (total + diff) // 2
    # 青木君の得点 = (total - diff) // 2
    aoki = (total - diff) // 2
    
    print(takahashi, aoki)

if __name__ == "__main__":
    main()

---

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