Overview

In this game, \(N\) cards are arranged in a row, and two players take turns picking a card from either end. Both players try to maximize “my score − opponent’s score,” and we need to determine each player’s final score.

Analysis

The key insight of this problem is that “maximizing one’s own score” is equivalent to “maximizing (one’s own score) − (opponent’s score)”.

1. Failure of Greedy Approach

The greedy strategy of “always take the larger number available at the ends” does not work. For example, if the cards are [10, 100, 10], if the first player takes the 10 at an end, the second player can then take the 100 in the center. The first player may need to deliberately take a smaller number to prevent the opponent from accessing a larger number on the next turn.

2. Using Dynamic Programming (Interval DP)

The game state is determined by “the range of remaining cards.” Define \(dp[i][j]\) as “the maximum value of (my score − opponent’s score) that the current player can achieve when the game starts with cards from the \(i\)-th to the \(j\)-th remaining.”

• Base case (when there is 1 card): \(dp[i][i] = A_i\) (since the only option is to take that one card)

• Transition (when there are multiple cards): The current player has two choices: “take the left end \(A_i\)” or “take the right end \(A_j\).”

  • Taking the left end: the resulting difference is \(A_i - dp[i+1][j]\)
  • Taking the right end: the resulting difference is \(A_j - dp[i][j-1]\)

  The larger of these two becomes the value of \(dp[i][j]\). \(dp[i][j] = \max(A_i - dp[i+1][j], A_j - dp[i][j-1])\)

3. Computing Individual Scores

Let \(D\) be “Takahashi’s score − Aoki’s score” at the end of the game. Let \(S\) be the sum of all cards. If Takahashi’s score is \(T\) and Aoki’s score is \(A\), the following system of equations holds: 1. \(T + A = S\) 2. \(T - A = D\)

Solving this gives \(T = (S + D) / 2\), \(A = (S - D) / 2\), yielding each player’s score.

Algorithm

1. Use interval DP to compute the “score difference \(D\)” for the state where all cards are present.
2. To improve computational efficiency, reuse a 1-dimensional array instead of a 2-dimensional array to save space (compute results for length \(L\) from results for length \(L-1\)).
3. Compute the total sum \(S\) of all cards.
4. Use the formulas above to calculate \(T\) and \(A\), and output them.

Complexity

• Time complexity: \(O(N^2)\)
  • The interval length \(L\) varies from \(1\) to \(N\), and for each \(L\), we iterate over starting positions \(i\), resulting in approximately \(N^2/2\) loop iterations. For \(N=3000\), this is about \(9 \times 10^6\) operations, which fits within the time limit even in Python with efficient implementation.
• Space complexity: \(O(N)\)
  • By reusing a 1-dimensional DP table, memory usage is kept low.

Implementation Notes

• Optimization in Python: Since Python’s loops are slow, we leverage the zip function and list comprehensions to delegate inner loops to fast C-level implementations.

• Index management: By increasing the interval length as \(1, 2, \dots, N\), we control the computation order so that results from “the previous step (shorter intervals)” are always available for reference.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.