Summary

Arrange the scores written on the cards in descending order, then calculate the total difference (Takahashi − Aoki) when the first and second players alternately take cards in that order.

Analysis

In this game, each turn a player can choose “any one card remaining.” Therefore, if both players aim to maximize their own score, the optimal strategy is to take the largest remaining card at each turn.

This is because if at some turn a player does not take the maximum value \(x\) and instead takes a smaller value \(y(<x)\): - Their own score becomes \(y\) instead of \(x\), resulting in a loss - Moreover, the opponent is likely to take \(x\) on their next turn (= the difference worsens even further)

In other words, choosing anything other than the maximum is never advantageous in that situation. Therefore, when both players play optimally, the cards are taken in descending order.

A naive approach like “searching the game tree to find the optimal strategy” would have close to \(N!\) possible choices, causing an explosion that is far too slow for \(N \le 2\times 10^5\) (TLE). Thanks to the observation above, this problem can actually be solved by simply sorting and alternately adding and subtracting.

Example: \(A=[3,1,4,1,5]\) Sort in descending order: \([5,4,3,1,1]\) Takahashi: \(5+3+1=9\), Aoki: \(4+1=5\), difference is \(9-5=4\)

Algorithm

1. Sort array \(A\) in descending order.
2. Iterate from the beginning:
   • Even-indexed elements (\(0,2,4,\dots\)) are taken by Takahashi, so add to the difference
   • Odd-indexed elements (\(1,3,5,\dots\)) are taken by Aoki, so subtract from the difference
3. Output the final difference.

This is a direct implementation of the fact that “cards are taken in descending order.”

Complexity

• Time complexity: \(O(N\log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the array)

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) up to \(2\times 10^5\), the total can be as large as approximately \(2\times 10^{14}\). Python’s int handles this without issues.

• Since input can be large, using sys.stdin.readline ensures stability.

• Using enumerate to check index parity and doing diff += a / diff -= a makes the code concise.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    diff = 0
    for i, a in enumerate(A):
        if i % 2 == 0:
            diff += a
        else:
            diff -= a
    print(diff)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.