Overview

This is a game where Takahashi and Aoki take turns picking one card at a time from \(N\) cards. We need to find the final score difference (Takahashi - Aoki) when both players act to maximize their own scores.

Analysis

The key to this problem is thinking about “what is the optimal strategy for each player?”

In this problem’s rules, there are no special conditions such as “picking a certain card changes the value of other cards.” For any card, the moment it is picked, its score is directly added to the player’s total.

In such a situation, when it’s your turn, prioritizing the card with the highest score among those remaining is always the best choice.

Why is picking in “descending order” optimal?

For example, suppose the card scores are \([10, 8, 5]\), and first-player Takahashi chooses \(8\) instead of \(10\). Then second-player Aoki would without hesitation choose \(10\) from the remaining \([10, 5]\). - If Takahashi chooses \(10\): Takahashi \(10 + 5 = 15\) points, Aoki \(8\) points (difference is \(+7\)) - If Takahashi chooses \(8\): Takahashi \(8 + 5 = 13\) points, Aoki \(10\) points (difference is \(+3\))

As shown, deliberately picking a smaller value only lets your opponent take the larger value, with no benefit to yourself. Therefore, both players will always continue to pick “the current maximum value.”

Algorithm

1. Sort the given list of card scores \(A\) in descending order (largest first).
2. For the sorted list, assign cards alternately to first-player Takahashi and second-player Aoki.
   • The 1st, 3rd, 5th, … cards (even indices) go to Takahashi.
   • The 2nd, 4th, 6th, … cards (odd indices) go to Aoki.
3. Output the value of Takahashi’s total score minus Aoki’s total score.

Complexity

• Time complexity: \(O(N \log N)\)
  • Sorting \(N\) elements takes \(O(N \log N)\). The subsequent sum calculation is \(O(N)\), so sorting determines the overall complexity.
  • Since \(N \leq 2 \times 10^5\), this complexity is well within the time limit.
• Space complexity: \(O(N)\)
  • An array is needed to store the \(N\) input scores.

Implementation Notes

• In Python, you can easily sort in descending order using list.sort(reverse=True).

• By utilizing slicing (a[0::2] and a[1::2]), you can write the process of alternately extracting elements and summing them very concisely.

• Since the values of \(A_i\) can be as large as \(10^9\), the total may exceed a 32-bit integer type. However, Python automatically handles arbitrary-precision integers, so there is no concern about overflow.

  Source Code

import sys

def solve():
    # 入力を標準入力からすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: カードの枚数
    n = int(input_data[0])
    # A: 各カードの得点
    a = list(map(int, input_data[1:]))
    
    # 得点を降順（大きい順）にソートする
    # 各プレイヤーは自分の得点を最大化するために、常に残っているカードの中で最大のものを取る
    a.sort(reverse=True)
    
    # 高橋君は1番目, 3番目, 5番目... のカードを取る（0-indexedでは偶数番目）
    # 青木君は2番目, 4番目, 6番目... のカードを取る（0-indexedでは奇数番目）
    takahashi_score = sum(a[0::2])
    aoki_score = sum(a[1::2])
    
    # （高橋君の得点）−（青木君の得点）を出力
    print(takahashi_score - aoki_score)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-preview.