Overview

This is a game where two players take turns picking cards, and we need to find the score difference when both players play optimally. The optimal strategy can be achieved using a greedy approach: “always take the card with the highest score among the remaining cards.”

Analysis

Key Insight

In this game, when both players “maximize their own score,” what actions are optimal?

Intuitively, it seems optimal to take the card with the highest score among the remaining cards. This is indeed the correct strategy.

Why is the Greedy Approach Optimal?

For example, suppose the remaining cards are \([10, 5, 3]\) and it’s Takahashi’s turn.

• If Takahashi takes \(10\), Aoki can take at most \(5\)
• If Takahashi takes \(5\), Aoki can take \(10\)

If Takahashi takes anything other than \(10\), that \(10\) will definitely be taken by Aoki. In other words, if you don’t take the maximum card, it goes to your opponent.

To maximize your own score, it’s also important not to give high cards to your opponent. Therefore, the greedy approach of always taking the maximum card is optimal.

Problems with a Naive Approach

If you try to solve this using dynamic programming (DP) or game tree search, the number of states becomes enormous and may result in TLE. However, since this problem can be solved in \(O(N \log N)\) using a greedy approach, such complex approaches are unnecessary.

Algorithm

1. Sort: Sort the cards in descending order (from largest to smallest)
2. Distribute alternately: Go through the sorted array in order:
   • Indices \(0, 2, 4, \ldots\) (odd-numbered cards) go to Takahashi’s score
   • Indices \(1, 3, 5, \ldots\) (even-numbered cards) go to Aoki’s score
3. Calculate the difference: Subtract Aoki’s total score from Takahashi’s total score

Concrete Example

For \(N = 4\), \(A = [3, 1, 4, 5]\):

1. After sorting in descending order: \([5, 4, 3, 1]\)
2. Distribution:
   • Takahashi: \(5 + 3 = 8\) (indices 0, 2)
   • Aoki: \(4 + 1 = 5\) (indices 1, 3)
3. Answer: \(8 - 5 = 3\)

Complexity

• Time complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(N)\) for calculating scores
• Space complexity: \(O(N)\)
  • Array to store the card scores

Implementation Notes

• Descending sort: Using sort(reverse=True) sorts in descending order
• Turn determination: If index \(i\) is even, it’s Takahashi’s turn; if odd, it’s Aoki’s turn (check with \(i \% 2 == 0\))
• Overflow caution: Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can be approximately \(2 \times 10^{14}\). In Python, there’s no need to worry about integer overflow, but in C++ and similar languages, you need to use long long

Source Code

n = int(input())
a = list(map(int, input().split()))

# When both players play optimally, the optimal strategy for each player
# is to take the card with the highest score among the remaining cards
a.sort(reverse=True)

takahashi = 0
aoki = 0

for i in range(n):
    if i % 2 == 0:  # Takahashi's turn (0, 2, 4, ...)
        takahashi += a[i]
    else:  # Aoki's turn (1, 3, 5, ...)
        aoki += a[i]

print(takahashi - aoki)

---

This editorial was generated by claude4.5opus.