概要

2人のプレイヤーが交互にカードを取り合うゲームで、両者が最適にプレイしたときの得点差を求める問題です。最適戦略は「常に残っているカードの中で最大の得点を取る」という貪欲法で実現できます。

考察

重要な気づき

このゲームで両者が「自分の得点を最大化」するとき、どのような行動が最適でしょうか？

直感的に考えると、残っているカードの中で最も得点の高いカードを取るのが最適に思えます。これは実際に正しい戦略です。

なぜ貪欲法が最適か？

例えば、残りカードが \([10, 5, 3]\) で高橋君のターンだとします。

• 高橋君が \(10\) を取ると、青木君は最大でも \(5\) を取れます
• 高橋君が \(5\) を取ると、青木君は \(10\) を取れてしまいます

高橋君が \(10\) 以外を取ると、その \(10\) は必ず青木君に取られます。つまり、最大のカードを取らないと、それは相手に渡ることになります。

自分の得点を最大化するためには、相手に高いカードを渡さないことも重要です。したがって、常に最大のカードを取る貪欲法が最適となります。

素朴なアプローチの問題点

もし動的計画法（DP）やゲーム木の探索で解こうとすると、状態数が膨大になり TLE になる可能性があります。しかし、この問題は貪欲法で \(O(N \log N)\) で解けるため、そのような複雑なアプローチは不要です。

アルゴリズム

1. ソート: カードを得点の降順（大きい順）にソートする
2. 交互に分配: ソートされた配列を順に見て、
   • インデックス \(0, 2, 4, \ldots\)（奇数番目のカード）は高橋君の得点
   • インデックス \(1, 3, 5, \ldots\)（偶数番目のカード）は青木君の得点
3. 差を計算: 高橋君の得点の合計から青木君の得点の合計を引く

具体例

\(N = 4\)、\(A = [3, 1, 4, 5]\) の場合：

1. 降順ソート後: \([5, 4, 3, 1]\)
2. 分配:
   • 高橋君: \(5 + 3 = 8\)（インデックス 0, 2）
   • 青木君: \(4 + 1 = 5\)（インデックス 1, 3）
3. 答え: \(8 - 5 = 3\)

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 得点の計算に \(O(N)\)
• 空間計算量: \(O(N)\)
  • カードの得点を格納する配列

実装のポイント

• 降順ソート: sort(reverse=True) を使うと、大きい順にソートできます

• ターンの判定: インデックス \(i\) が偶数なら高橋君のターン、奇数なら青木君のターンと判定できます（\(i \% 2 == 0\) で判定）

• オーバーフロー注意: \(A_i\) が最大 \(10^9\) で \(N\) が最大 \(2 \times 10^5\) なので、合計は最大約 \(2 \times 10^{14}\) になります。Python では整数オーバーフローの心配はありませんが、C++ などでは long long を使う必要があります

  ソースコード

n = int(input())
a = list(map(int, input().split()))

# 両者が最適にプレイする場合、各プレイヤーは残っているカードの中で
# 最も得点の高いカードを取るのが最適戦略
a.sort(reverse=True)

takahashi = 0
aoki = 0

for i in range(n):
    if i % 2 == 0:  # 高橋君のターン（0, 2, 4, ...）
        takahashi += a[i]
    else:  # 青木君のターン（1, 3, 5, ...）
        aoki += a[i]

print(takahashi - aoki)

---

この解説は claude4.5opus によって生成されました。