概要

\(N\) 人のメンバーから \(2\) 人を選んで能力値の和を最大化する問題です。能力値が最も高い \(2\) 人を選べばよいという、シンプルな貪欲法で解けます。

考察

重要な気づき

ペアの総合力（\(2\) 人の能力値の和）を最大にしたいので、直感的に「能力値が大きい人を \(2\) 人選べばよい」と考えられます。

これが正しいことを確認してみましょう。\(2\) 人の能力値を \(A_i\) と \(A_j\)（\(i \neq j\)）とすると、総合力は \(A_i + A_j\) です。この値を最大化するには： - まず \(A_i\) をできるだけ大きくする → 能力値が最大の人を選ぶ - 次に \(A_j\) をできるだけ大きくする → 能力値が \(2\) 番目に大きい人を選ぶ

よって、能力値の上位 \(2\) 人を選ぶのが最適です。

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

すべてのペアの組み合わせを試す方法も考えられます。\(N\) 人から \(2\) 人を選ぶ組み合わせは \(\frac{N(N-1)}{2}\) 通りあるため、\(N = 2 \times 10^5\) のとき約 \(2 \times 10^{10}\) 回の計算が必要になり、TLE（時間超過）になってしまいます。

解決策

配列をソートして上位 \(2\) つの要素を取り出せば、\(O(N \log N)\) で解けます。

アルゴリズム

1. 能力値の配列 \(A\) を降順（大きい順）にソートする
2. ソート後の配列の先頭 \(2\) 要素（\(A[0]\) と \(A[1]\)）が能力値の上位 \(2\) 人
3. \(A[0] + A[1]\) を出力する

具体例

\(N = 5\)、\(A = [3, 1, 4, 1, 5]\) の場合： - 降順にソート: \(A = [5, 4, 3, 1, 1]\) - 上位 \(2\) 人の能力値: \(5\) と \(4\) - 総合力の最大値: \(5 + 4 = 9\)

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)、上位 \(2\) 要素の取得に \(O(1)\)
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を格納するための領域

実装のポイント

• Python では sort(reverse=True) で降順ソートができます

• 昇順ソートして末尾 \(2\) 要素（\(A[N-2]\) と \(A[N-1]\)）を取る方法でも同じ結果が得られます

• 能力値の最大値が \(10^9\) なので、\(2\) 人の和は最大 \(2 \times 10^9\) となりますが、Python では整数のオーバーフローを気にする必要はありません

  ソースコード

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(A[0] + A[1])

---

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