概要

\(N\) 個のチームの募金額が与えられ、選んだチームの募金額の合計が全体の総額の半分以上になるようにするための最小のチーム数を求める問題です。

考察

選ぶチーム数を最小にするためには、1つのチームが集めた募金額が大きいものから順に選んでいくのが最適です。

なぜなら、少ないチーム数で目標額を達成するには、1つのチームが持つ募金額が大きいほど有利だからです。もし小さい額のチームを選んだ場合、それをより大きな額のチームに置き換えれば、より少ないチーム数で目標を達成できることになります。

したがって、「募金額が大きいチームから順に選んでいく」という貪欲法（その時点での最善の選択を繰り返す手法）で解を求めることができます。

アルゴリズム

1. 全チームの募金額の総和 \(T\) を計算します。
2. 達成すべき目標額である \(\lceil T / 2 \rceil\) を計算します。
3. 募金額のリストを降順（大きい順）にソートします。
4. ソートしたリストの先頭から順に金額を足していき、合計が目標額以上になった瞬間にループを終了し、その時点でのチーム数を出力します。

計算量

• 時間計算量: \(O(N \log N)\) （リストのソートが最も計算時間を要する処理です）
• 空間計算量: \(O(N)\) （入力された募金額のリストを保持するため）

実装のポイント

• 入力の制約が \(N \le 10^6\) と大きいため、Pythonでは通常の input() を使うと入力の読み込みだけで実行時間制限を超える（TLEする）可能性があります。sys.stdin.buffer.read().split() を使って一度に全入力を読み込むことで、入力を高速に処理できます。

• 目標額 \(\lceil T / 2 \rceil\) は、\(T\) が奇数の場合は T // 2 + 1、偶数の場合は T // 2 となります。これをプログラムで簡単に表現するために (T + 1) // 2 と記述すると、1行で切り上げの計算ができます。

• リストを降順にソートする際は、A.sort(reverse=True) を使用します。

  ソースコード

import sys

def solve():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    A = [int(x) for x in data[1:N+1]]
    
    total = sum(A)
    target = (total + 1) // 2
    
    A.sort(reverse=True)
    
    cur = 0
    ans = 0
    for x in A:
        cur += x
        ans += 1
        if cur >= target:
            break
            
    print(ans)

if __name__ == "__main__":
    solve()

この解説は or-glm5.2-high によって生成されました。