概要

カードに書かれた得点を高い順に並べ、先手・後手が交互にその順で取るときの合計差（高橋−青木）を計算します。

考察

このゲームでは、各ターンに「残っている中から好きな1枚」を選べます。したがって両者とも 自分の得点を最大化するなら、その時点で残っている最大のカードを取る のが最適です。

なぜなら、あるターンで最大値 \(x\) を取らずにそれより小さい \(y(<x)\) を取ると、 - 自分の得点は \(x\) ではなく \(y\) になって損をする - しかも次の相手のターンで \(x\) を取られてしまう可能性が高い（＝差がさらに悪化）

つまり「最大を取る」以外の選択は、少なくともその場で有利になりません。よって両者が最適にプレイすると、カードは 大きい順に 取られていきます。

素朴に「ゲーム木を探索して最適戦略を求める」ようなことをすると、選び方が \(N!\) 通りに近く爆発し、\(N \le 2\times 10^5\) では到底間に合いません（TLE）。
この問題は上の観察により、実際には 並べ替えて交互に加減算するだけ で解けます。

例：\(A=[3,1,4,1,5]\)
降順にして \([5,4,3,1,1]\)
高橋：\(5+3+1=9\)、青木：\(4+1=5\)、差は \(9-5=4\)

アルゴリズム

1. 配列 \(A\) を降順ソートする。
2. 先頭から順に見ていき、
   • 偶数番目（\(0,2,4,\dots\)）は高橋が取るので差に加算
   • 奇数番目（\(1,3,5,\dots\)）は青木が取るので差から減算
3. 最終的な差を出力する。

これは「大きい順に取られる」ことをそのまま実装したものです。

計算量

• 時間計算量: \(O(N\log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（配列保持）

実装のポイント

• \(A_i\) が最大 \(10^9\)、\(N\) が最大 \(2\times 10^5\) なので、合計は最大で \(2\times 10^{14}\) 程度になります。Python の int なら問題ありません。

• 入力が大きいので sys.stdin.readline を使うと安定します。

• enumerate で添字の偶奇を見て diff += a / diff -= a とすると簡潔に書けます。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。