概要

\(N\) 人のメンバーから異なる \(2\) 人を選び、その能力値の和（総合力）を最大化する問題です。

考察

この問題で求めたいのは、配列 \(A\) の中から異なるインデックス \(i, j\) を選んだときの \(A_i + A_j\) の最大値です。

重要な気づき

和を最大にするためには、「全メンバーの中で最も能力値が高い人」と「次に能力値が高い人」をペアにすればよいことが分かります。 例えば、能力値が \([3, 8, 5, 1, 8]\) であれば、最大値の \(8\) と、その次に大きい \(8\)（または \(5\)）を足した \(16\) が最大となります。

なぜ素朴な方法ではいけないのか

すべてのペアを調べる方法（二重ループ）を考えてみます。 この場合、ペアの数は \(\frac{N(N-1)}{2}\) 通り存在します。制約の \(N = 2 \times 10^5\) を代入すると、約 \(2 \times 10^{10}\) 回の計算が必要になります。 一般的なプログラミングコンテストの実行時間制限（2秒程度）では、1秒間にこなせる計算量は \(10^8\) 回程度であるため、この方法では「実行時間制限超過 (TLE)」になってしまいます。

したがって、すべてのペアを調べずに、効率よく最大値と2番目の値を見つける必要があります。

アルゴリズム

配列をソート（並べ替え）する手法が最もシンプルです。

1. 与えられた \(N\) 個の能力値を降順（大きい順）にソートします。
2. ソート後の配列の先頭 \(2\) つの要素（\(A_0\) と \(A_1\)）を取り出します。
3. それらの和を出力します。

ソートアルゴリズムは非常に高速であるため、今回の制約下でも十分に間に合います。

計算量

• 時間計算量: \(O(N \log N)\)
  • \(N\) 個の要素のソートには \(O(N \log N)\) の時間がかかります。\(N = 2 \times 10^5\) のとき、\(N \log N\) は約 \(3.6 \times 10^6\) 程度であり、制限時間内に余裕を持って計算可能です。
• 空間計算量: \(O(N)\)
  • \(N\) 人分の能力値をリストに格納するためのメモリが必要です。

実装のポイント

• 大きな入力の読み込み: \(N\) が \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを使って一括で入力を読み込むと高速です。

• ソートの順序: a.sort(reverse=True) とすることで、大きい順に並べ替えることができます。昇順（小さい順）でソートした場合は、後ろから2つの要素（a[-1] と a[-2]）を参照します。

  ソースコード

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    a = list(map(int, input_data[1:]))
    
    # 能力値を降順（大きい順）にソート
    a.sort(reverse=True)
    
    # 上位2人の能力値の和が最大値となる
    max_total_power = a[0] + a[1]
    
    # 結果を出力
    print(max_total_power)

if __name__ == "__main__":
    solve()

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