概要

\(N\) 枚のカードが一列に並んだ状態で、2人のプレイヤーが両端のいずれかからカードを取り合うゲームです。互いに「自分の得点 － 相手の得点」を最大化しようとする状況において、最終的なそれぞれの得点を求めます。

考察

この問題のポイントは、「自分の得点を最大化する」ことが「（自分の得点）－（相手の得点）を最大化する」ことと同義であるという点です。

1. 貪欲法の失敗

「その場で最も大きい数字を取る」という貪欲な戦略はうまくいきません。例えば、カードが [10, 100, 10] と並んでいる場合、先手が端の 10 を取ると、後手に中央の 100 を取られてしまいます。先手はあえて小さい数字を取ることで、次に相手に大きな数字を取らせないように立ち回る必要があります。

2. 動的計画法（区間DP）の活用

ゲームの状態は「残っているカードの範囲」で決まります。 \(dp[i][j]\) を「左から \(i\) 番目から \(j\) 番目までのカードが残っている状態からゲームを始めたとき、その時の手番のプレイヤーが達成できる（自分の得点 － 相手の得点）の最大値」と定義します。

• ベースケース（カードが1枚のとき）: \(dp[i][i] = A_i\) （その1枚を取るしかないため）

• 遷移（カードが複数枚のとき）: 手番のプレイヤーには「左端 \(A_i\) を取る」か「右端 \(A_j\) を取る」かの2つの選択肢があります。

  • 左端を取る場合：得られる差分は \(A_i - dp[i+1][j]\)
  • 右端を取る場合：得られる差分は \(A_j - dp[i][j-1]\)

  これら2つのうち、大きい方が \(dp[i][j]\) の値となります。 \(dp[i][j] = \max(A_i - dp[i+1][j], A_j - dp[i][j-1])\)

3. 個別の得点の算出

ゲーム終了時の「高橋君の得点 － 青木君の得点」を \(D\) とします。また、全カードの合計を \(S\) とします。 高橋君の得点を \(T\)、青木君の得点を \(A\) とすると、以下の連立方程式が成り立ちます。 1. \(T + A = S\) 2. \(T - A = D\)

これを解くと、 \(T = (S + D) / 2\), \(A = (S - D) / 2\) となり、それぞれの得点が求まります。

アルゴリズム

1. 区間DPを用いて、全てのカードがある状態での「得点差 \(D\)」を計算します。
2. 計算効率を上げるため、2次元配列ではなく1次元配列を使い回すことで空間計算量を節約します（現在の長さ \(L\) の結果を、長さ \(L-1\) の結果から計算する）。
3. 全カードの合計値 \(S\) を計算します。
4. 上記の式を用いて \(T\) と \(A\) を算出し、出力します。

計算量

• 時間計算量: \(O(N^2)\)
  • カードの区間の長さ \(L\) を \(1\) から \(N\) まで変化させ、各 \(L\) について開始位置 \(i\) を走査するため、ループ回数は約 \(N^2/2\) 回となります。\(N=3000\) の場合、\(9 \times 10^6\) 程度の計算量であり、Pythonでも効率的に実装すれば制限時間内に収まります。
• 空間計算量: \(O(N)\)
  • 1次元のDPテーブルを使い回すことで、メモリ使用量を抑えています。

実装のポイント

• Pythonでの高速化: Pythonはループが遅いため、zip 関数やリスト内包表記を活用して、内部的なループを高速なC言語実装に任せる工夫をしています。

• インデックス管理: 区間の長さを \(1, 2, \dots, N\) と増やしていくことで、常に「一歩手前の状態（短い区間）」の結果を参照できるように計算順序を制御しています。

  ソースコード

import sys

def solve():
    # 標準入力から全データを読み込み、空白で分割してリスト化します。
    # N=3000程度の制約であれば、この方法が高速です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（カードの枚数）と A（カードの数値配列）を取得します。
    n = int(input_data[0])
    a = [int(x) for x in input_data[1:]]
    
    if n == 0:
        print(0, 0)
        return

    # dp[i] は、現在の長さの区間において「（自分の得点）-（相手の得点）」の最大値を保持します。
    # 初期状態として、区間の長さが1の場合（各カードが1枚のみの場合）の値を設定します。
    dp = a
    
    # 区間の長さを2からNまで順に更新していきます。
    # L は (現在の長さ - 1) を表し、右端のインデックス計算に利用します。
    for L in range(1, n):
        # 以下の漸化式を各 i について計算します：
        # dp_new[i] = max(a[i] - dp_old[i+1], a[i+L] - dp_old[i])
        # Python 3 で高速に動作させるため、リスト内包表記と zip を使用します。
        
        # zip に渡す各要素の役割：
        # al: 左端のカードの値 a[i]
        # dpl: 左端を除いた残り区間の最大差 dp_old[i+1]
        # ar: 右端のカードの値 a[i+L]
        # dpr: 右端を除いた残り区間の最大差 dp_old[i]
        
        # zip は最短のイテラブルに合わせて停止するため、
        # ループ回数は自然に (n - L) 回（現在の区間の数）となります。
        dp = [
            (al - dpl if al - dpl > ar - dpr else ar - dpr)
            for al, dpl, ar, dpr in zip(a, dp[1:], a[L:], dp)
        ]
        
    # 全てのカード（長さNの区間）に対する最終的な（高橋君の得点 - 青木君の得点）
    diff = dp[0]
    
    # 全カードの合計値
    total_sum = sum(a)
    
    # 高橋君の得点を T、青木君の得点を A とすると：
    # 1) T + A = total_sum
    # 2) T - A = diff
    # これらを解くと：
    # 2T = total_sum + diff  => T = (total_sum + diff) / 2
    # 2A = total_sum - diff  => A = (total_sum - diff) / 2
    takahashi_score = (total_sum + diff) // 2
    aoki_score = (total_sum - diff) // 2
    
    # 結果を出力します。
    sys.stdout.write(f"{takahashi_score} {aoki_score}\n")

if __name__ == '__main__':
    solve()

---

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