概要

左右どちらかの端からカードを取り合う 2 人ゲームを、両者最適行動として解析し、高橋君・青木君それぞれの最終得点を求めます。

考察

このゲームは「現在残っている区間（連続部分列）」だけで状態が決まります。
しかし、各手番で左/右の 2 通りに分岐するため、素朴に全探索すると分岐数は最大で \(2^N\) となり、\(N \le 3000\) では到底間に合いません。

ここで重要なのは、「（自分の得点）−（相手の得点）」を最大化するという目的です。
この“差”に注目すると、次の性質が使えます：

• ある区間 \([l, r]\) が残っていて「これから手番の人」を current とすると、
  • 左端 \(A_l\) を取ると、current は \(A_l\) を得る
  • 次の手番では相手が区間 \([l+1, r]\) から最適にプレイし、差（相手−自分）を最大化する
• つまり、current から見た差（current−other）は
  • 左を取る場合：\(A_l - \text{dp}[l+1][r]\)
  • 右を取る場合：\(A_r - \text{dp}[l][r-1]\) の最大になります（「次は相手番」なので差がマイナスで効くのがポイント）。

このように「差」の DP にすると、先手・後手や手番の偶奇を明示せずに解けます。

さらに、最終的に求めたいのは両者の得点そのものですが、全カード和を \(S=\sum A_i\)、最終的な差を \(D=(\text{高橋} - \text{青木})\) とすると、 - \(\text{高橋} + \text{青木} = S\) - \(\text{高橋} - \text{青木} = D\) より - \(\text{高橋} = \dfrac{S + D}{2}\)、\(\text{青木} = S - \text{高橋}\) で復元できます（\(S\) と \(D\) は同じ偶奇になるので割り切れます）。

アルゴリズム

1. DP の定義

区間 DP を考えます。

• \(\text{dp}[l][r]\)：区間 \([l, r]\) のカードが残っていて「次に取る人（current）」が最適に行動するときの
  （current の得点）−（other の得点）の最大値

2. 遷移

区間 \([l, r]\) で current ができる選択は左右どちらか 1 枚：

• 左端を取る：得る点は \(A_l\)、残りは \([l+1, r]\)
  次は相手番なので、相手視点の差が \(\text{dp}[l+1][r]\) だけ有利になる。
  よって current 視点の差は
  $\( A_l - \text{dp}[l+1][r] \)$

• 右端を取る：同様に
  $\( A_r - \text{dp}[l][r-1] \)$

よって $\( \text{dp}[l][r] = \max\left(A_l - \text{dp}[l+1][r],\; A_r - \text{dp}[l][r-1]\right) \)$

3. 初期値

長さ 1 の区間では 1 枚取るだけなので $\( \text{dp}[i][i] = A_i \)$

4. 1 次元への圧縮

実装では \(\text{dp}[l][r]\) を「区間の長さを伸ばしながら」計算し、必要なのは - \(\text{dp}[l+1][r]\)（同じ長さで \(l\) が 1 大きい） - \(\text{dp}[l][r-1]\)（1 つ短い区間） のみです。

提示コードでは - 現在の長さに対する \(\text{dp}[l][r]\) を 1 次元配列 dp[l] で持つ - 長さを 2,3,… と増やしながら dp[l] を更新 という形で \(O(N)\) メモリにしています。

5. 得点の復元

最終的に dp[0] が区間 \([0, N-1]\) における差 \(D\) です。
全体和 \(S\) を使って $\( \text{高橋}=\frac{S+D}{2},\quad \text{青木}=S-\text{高橋} \)$ を出力します。

計算量

• 時間計算量: \(O(N^2)\)（区間の数が約 \(N^2/2\)）
• 空間計算量: \(O(N)\)（1 次元 DP）

実装のポイント

• DP は「差（current−other）」で持つと、手番の偶奇を考えずに遷移が書けます。

• 1 次元圧縮では更新順が重要です。提示コードは「区間長を固定して左端 \(l\) を増やす」形で、必要な dp[l+1] と（更新前の）dp[l] を正しく参照できる順になっています。

• 値が最大で \(10^9\)、\(N=3000\) なので合計は \(3\times 10^{12}\) 程度になり得ますが、Python の整数は任意精度なのでオーバーフローは心配不要です。

  ソースコード

import sys

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

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

    d = dp[0]
    takahashi = (s + d) // 2
    aoki = s - takahashi
    sys.stdout.write(f"{takahashi} {aoki}")

if __name__ == "__main__":
    main()

---

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