Overview

A problem where cards are removed from the left and right ends, and we need to determine the result of a game where the first player maximizes and the second player minimizes the value of the last remaining card.

Analysis

In this problem, we need to determine which card ultimately remains (i.e., what the score will be) under the assumption that both players play optimally.

A naive approach would be to simulate the game progression through exhaustive search, but at each step there is a branching choice between left and right, causing the overall search space to become exponential in time. Therefore, an efficient solution is needed.

The key insight is that “the game state at any point can be represented as a contiguous interval.” In other words, no matter how many operations are performed, the remaining cards always form a contiguous subarray. For example, if 3 cards have been taken from the left and 2 from the right, what remains is a contiguous interval in the middle.

Using this property, we can apply a technique called “interval DP (dynamic programming).” Specifically, we define dp[l][r] as “the final score when the remaining cards are the interval from A[l] to A[r].”

Next, we consider the transitions. For the current interval [l, r], the next move can remove either the left end l or the right end r. Which one is chosen depends on the current player’s objective (maximize/minimize the score).

Furthermore, we need to determine whose turn it is. Starting with \(N\) cards, and the interval [l, r] having length \(r-l+1\), the number of operations performed is \(N - (r - l + 1)\). If this is even, it’s the first player’s turn; if odd, it’s the second player’s turn.

By filling in dp[l][r] in order from smaller intervals, the final answer is dp[0][N-1].

Algorithm

Using interval DP (dynamic programming), we recursively compute the score for interval [l, r].

Steps

1. Define dp[l][r] as “the final score when interval [l, r] remains.”
2. Base case: When the interval length is 1 (i.e., \(l = r\)), the score is the value of that card:

   
   dp[i][i] = A[i]
   

3. For intervals of length 2 or more, compute in order of increasing interval length:
   • If it’s the first player’s turn (even number of operations), choose left or right to maximize the score
   • If it’s the second player’s turn (odd number of operations), choose left or right to minimize the score

The transition formulas are as follows:

• First player’s turn (score maximization): $\( dp[l][r] = \max(dp[l+1][r],\ dp[l][r-1]) \)$

• Second player’s turn (score minimization): $\( dp[l][r] = \min(dp[l+1][r],\ dp[l][r-1]) \)$

The final answer is dp[0][N-1].

Complexity

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

Since each interval [l, r] is processed exactly once, the time complexity is \(O(N^2)\). The dp table size is also \(N \times N\), so the space complexity is the same.

Implementation Notes

• By increasing the interval length starting from 2, we guarantee that all required information has already been computed.

• Turn calculation: If turn = N - (r - l + 1) is even, it’s the first player’s turn; if odd, it’s the second player’s turn.

• In Python, updating the DP with loops rather than recursion is safer and faster.

  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[l][r] := 残りがA[l], A[l+1], ..., A[r]のときのスコア
    dp = [[0]*N for _ in range(N)]
    
    # 初期化: 残り1枚の場合はその値がスコア
    for i in range(N):
        dp[i][i] = A[i]
    
    # 区間DP: len=2以上について計算
    for length in range(2, N+1):       # 残り枚数
        for l in range(N - length + 1): # 左端
            r = l + length - 1          # 右端
            # 先手のターンならスコアを最大化、後手のターンなら最小化
            # ターン数 = N - (r - l + 1) → 先手は偶数、後手は奇数
            turn = N - (r - l + 1)
            if turn % 2 == 0:  # 先手のターン（スコア最大化）
                dp[l][r] = max(dp[l+1][r], dp[l][r-1])
            else:              # 後手のターン（スコア最小化）
                dp[l][r] = min(dp[l+1][r], dp[l][r-1])
    
    print(dp[0][N-1])

if __name__ == "__main__":
    main()

---

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