概要

高橋君と青木君が交互にカードを取り、得点を最大化するゲームにおいて、両者が最適に戦略を取ったときの得点差（高橋君の得点 − 青木君の得点）を求めます。

考察

このゲームでは、各プレイヤーは自分の得点を最大化しようとしますが、同時に相手の得点を最小化することも考えなければなりません。つまり、ミニマックス法的な考え方が必要です。

しかし、この問題の特徴として「カードは順番に取られるが、どちらのプレイヤーも最適に動く」という点があります。重要な観察として、

• 各プレイヤーは常に残っている中で最も得点の高いカードを取るのが最適

という性質があります。なぜなら、自分にとっても相手にとっても高い価値のカードがある場合、それを相手に取られると自分の不利になるからです。

したがって、ゲームの進行としては：

1. 最初にカードを降順にソート
2. 先手（高橋君）は偶数インデックス（0, 2, 4, …）のカードを取り、
3. 後手（青木君）は奇数インデックス（1, 3, 5, …）のカードを取るのが最適

となります。

例えば、カードが [3, 1, 4] の場合： - ソートすると [4, 3, 1] - 高橋君は 4 と 1 を取り合計 5 - 青木君は 3 を取り合計 3 - 差は 5 - 3 = 2

このように、単純にソートして交互に取るだけで最適戦略になります。

アルゴリズム

1. カード列 \(A\) を降順にソート
2. 高橋君の得点：偶数インデックスの要素の和（A[0], A[2], A[4], ...）
3. 青木君の得点：奇数インデックスの要素の和（A[1], A[3], A[5], ...）
4. それらの差を出力

Pythonのスライス記法を使うと、以下のように簡潔に書けます： - 高橋君の得点：sum(A[::2]) - 青木君の得点：sum(A[1::2])

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(1)\)（入力を除けば定数メモリ）

実装のポイント

• ソートは降順に行うこと（得点が高い順）
• スライス A[::2] と A[1::2] を使って交互に和を取るのが簡潔で高速
• 入力の受け取りと変換を忘れずに：list(map(int, input().split()))

## ソースコード

```python
N = int(input())
A = list(map(int, input().split()))

A.sort(reverse=True)

takahashi = sum(A[::2])
aoki = sum(A[1::2])

print(takahashi - aoki)

---

この解説は qwen3-coder-480b によって生成されました。