概要

\(N\) 枚のカードを、高橋君と青木君が交互に1枚ずつ取っていくゲームです。両者が自分の得点を最大化するように行動したときの、最終的な得点差（高橋 - 青木）を求めます。

考察

この問題の鍵は、「各プレイヤーにとっての最適な戦略は何か」を考えることです。

今回のルールでは、「あるカードを取ることで他のカードの価値が変わる」といった特殊な条件はありません。どのカードも、取った瞬間にその得点がそのまま自分のスコアに加算されます。

このような状況では、自分の手番が回ってきたときに「場に残っているカードの中で最も得点が高いもの」を優先的に取ることが、常に最善の選択となります。

なぜ「大きい順」に取るのが最適なのか？

例えば、得点が \([10, 8, 5]\) というカードがあるとき、先手の高橋君が \(10\) ではなく \(8\) を選んだとしましょう。すると、後手の青木君は残った \([10, 5]\) から迷わず \(10\) を選びます。 - 高橋君が \(10\) を選んだ場合：高橋 \(10 + 5 = 15\)点、青木 \(8\)点（差は \(+7\)） - 高橋君が \(8\) を選んだ場合：高橋 \(8 + 5 = 13\)点、青木 \(10\)点（差は \(+3\)）

このように、わざと小さい値を取っても相手に大きい値を取られるだけで、自分にメリットはありません。したがって、両者は常に「現時点での最大値」を取り続けることになります。

アルゴリズム

1. 与えられたカードの得点リスト \(A\) を、降順（大きい順）にソートします。
2. ソートされたリストに対して、先手の高橋君と後手の青木君が交互にカードを割り当てます。
   • 1番目、3番目、5番目…（インデックスが偶数）のカードは高橋君のもの。
   • 2番目、4番目、6番目…（インデックスが奇数）のカードは青木君のもの。
3. 高橋君の合計点から青木君の合計点を引いた値を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の要素のソートに \(O(N \log N)\) かかります。その後の合計値の計算は \(O(N)\) なので、ソートが全体の計算量を決定します。
  • \(N \leq 2 \times 10^5\) なので、この計算量で十分に実行時間制限に間に合います。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の得点を保持するための配列が必要です。

実装のポイント

• Pythonでは list.sort(reverse=True) を使うことで、簡単に降順ソートが可能です。

• スライス機能（a[0::2] や a[1::2]）を利用すると、交互に要素を抽出して合計する処理を非常に簡潔に記述できます。

• \(A_i\) の値が最大 \(10^9\) と大きいため、合計値が 32bit 整数型を超えてしまう可能性がありますが、Pythonは自動的に多倍長整数として扱うため、オーバーフローの心配はありません。

  ソースコード

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()

この解説は gemini-3-flash-preview によって生成されました。