Overview

In a game where players take turns picking cards from the left or right end, and aim to maximize their final score difference, we determine the scores of Takahashi and Aoki when both play optimally.

Analysis

This game is a type of problem known as a “two-player zero-sum game,” where both players act to maximize “my score − opponent’s score.”

A naive approach would be to try all possible ways of picking cards via exhaustive search, but since there is a left/right choice at each turn and the search requires depth \(N\), the computation time is exponential. With \(N\) up to \(3000\), this is far too slow.

A greedy approach (e.g., always taking the largest available number) is also incorrect. This is because even if you gain a small advantage now, you might leave good cards for your opponent later.

Therefore, the effective approach is dynamic programming on intervals (interval DP), where we record “the maximum score difference the current player can achieve for a given remaining interval of cards.”

For an interval \([i, j]\), we define the optimal score difference as dp[i][j]. The current player can take either the left end \(A[i]\) or the right end \(A[j]\), after which it becomes the opponent’s turn. Since the opponent also plays optimally, the current player needs to maximize “the score of the taken card − the opponent’s optimal score difference in the next interval.”

For example, if the current player takes the left end in interval \([i, j]\): $\( \text{score difference} = A[i] - dp[i+1][j] \)\( Similarly, if taking the right end: \)\( \text{score difference} = A[j] - dp[i][j-1] \)$ The optimal play is to choose whichever is larger.

As the base case, when only one card remains (interval length is 1), the value of that card itself is the score difference.

Finally, what we computed is the “score difference.” Letting Takahashi’s score be \(T\) and Aoki’s score be \(A\): - \(T - A = \text{dp}[0][N-1]\) - \(T + A = \sum A\)

By solving these two simultaneous equations: $\( T = \frac{\text{sum} + \text{diff}}{2}, \quad A = \frac{\text{sum} - \text{diff}}{2} \)$

Algorithm

We use interval DP (dynamic programming).

• dp[i][j]: When the remaining cards span the interval from the \(i\)-th to the \(j\)-th card, the maximum score difference the current player can achieve in that interval.
• Transition: $\( dp[i][j] = \max(A[i] - dp[i+1][j],\ A[j] - dp[i][j-1]) \)$
• Base case: dp[i][i] = A[i]

We fill in the intervals in order from shortest to longest (bottom-up approach).

Complexity

• Time complexity: \(O(N^2)\)
• Space complexity: \(O(N^2)\)

Implementation Notes

• Allocate a 2D DP table and fill it starting from interval length 2 upward.

• When computing individual scores from the score difference and total sum, use // instead of / for integer division (safe in Python).

• sys.stdin.read is used for fast input reading.

  Source Code

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

---

This editorial was generated by qwen3-coder-480b.