Overview

Cards are arranged in a row, and first player Takahashi and second player Aoki alternately take a card from either the left end or the right end. The problem asks for the score difference (Takahashi’s total − Aoki’s total) when both players play optimally.

Analysis

This problem is a type of “two-player zero-sum finite deterministic perfect information game,” and interval DP (dynamic programming) is effective. A naive recursive search would have \(O(2^N)\) states, making computation impossible for \(N=3000\). Instead, we consider a DP that computes the optimal score difference for the interval \([l, r]\) with memoization.

The key observation is that the action changes depending on which player’s turn it is. Since the current player can be determined from the turn number (remaining number of cards), we define the DP state as the interval \([l, r]\) and compute the score difference (Takahashi − Aoki) when the player about to play in that interval acts optimally.

Algorithm

We define a two-dimensional array dp[l][r] as the score difference (Takahashi − Aoki) obtained from the remaining play when the cards in interval \([l, r]\) are left.

• When the number of remaining cards is \(length = r-l+1\), a total of \(n - length\) turns have elapsed. If this is even, it is Takahashi’s turn; if odd, it is Aoki’s turn.
• On Takahashi’s turn (\((n - length)\) % 2 == 0), he acts to maximize his own score. The score difference when taking the left end is \(V[l] + dp[l+1][r]\), and when taking the right end is \(V[r] + dp[l][r-1]\), so he chooses the maximum of these.
• On Aoki’s turn (\((n - length)\) % 2 == 1), he acts to minimize the score difference (Takahashi − Aoki), i.e., to maximize his own score. When taking the left end, the score difference is \(-V[l] + dp[l+1][r]\) (subtracting Aoki’s score \(V[l]\) from Takahashi’s score), and when taking the right end, it is \(-V[r] + dp[l][r-1]\), so he chooses the minimum of these.

We compute in order from smaller interval lengths, and ultimately dp[0][n-1] gives the overall score difference.

Complexity

• Time complexity: \(O(N^2)\)
  • The number of states is \(O(N^2)\), and each state is computed in constant time.
• Space complexity: \(O(N^2)\)
  • The DP table is an \(N \times N\) two-dimensional array.

Implementation Details

• Loop by increasing the interval length (length) from 1 to \(N\).

• For each length, move the left end l and compute the corresponding right end r = l + length - 1.

• Turn determination is done with (n - length) % 2 == 0, and processing is split between Takahashi and Aoki.

• When the interval length is 1, it is handled separately as a base case.

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    V = list(map(int, data[1:1+n]))
    
    dp = [[0] * n for _ in range(n)]
    
    for length in range(1, n+1):
        for l in range(0, n - length + 1):
            r = l + length - 1
            if (n - length) % 2 == 0:
                if length == 1:
                    dp[l][r] = V[l]
                else:
                    left_choice = V[l] + dp[l+1][r]
                    right_choice = V[r] + dp[l][r-1]
                    dp[l][r] = max(left_choice, right_choice)
            else:
                if length == 1:
                    dp[l][r] = -V[l]
                else:
                    left_choice = -V[l] + dp[l+1][r]
                    right_choice = -V[r] + dp[l][r-1]
                    dp[l][r] = min(left_choice, right_choice)
                    
    print(dp[0][n-1])

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.