概要

\(N\) 個のチームから選んだ募金額の合計が全体の半分以上（\(\lceil T/2 \rceil\) 以上）になるように、最小のチーム数を求める問題です。

考察

まず、選ぶチーム数を最小にしたいので、できるだけ多くの金額を効率よく稼げるチームを選ぶべきだと考えられます。

ここで重要な気づきは、「金額が大きいチームから順に選んでいくのが最適である」という点です。

なぜなら、同じ「選ぶチーム数」であっても、金額の大きいチームを優先して選んだ方が合計金額が大きくなるからです。たとえば \(k\) 個のチームを選ぶとき、金額の大きい上位 \(k\) 個を選べば、その組み合わせが取りうる合計金額の中で最大になります。したがって、目標金額を最も少ない個数で達成するには、大きい方から貪欲に選んでいけばよいのです。

具体例を考えてみましょう。チームの募金額が \(\{1, 3, 5, 4, 2\}\) の場合、総額は \(T = 15\)、目標は \(\lceil 15/2 \rceil = 8\) です。

• 大きい順に並べると \(\{5, 4, 3, 2, 1\}\)
• \(5\) を選ぶ → 合計 \(5\)（まだ \(8\) 未満）
• \(5 + 4 = 9\) → 合計 \(9\)（\(8\) 以上を達成！）

よって答えは \(2\) チームとなります。

なお、目標金額の計算で「半分以上（\(\lceil T/2 \rceil\) 以上）」という条件に注意が必要です。\(T\) が奇数のときに単純に \(T/2\) とすると切り捨てが起きてしまうため、\(\lceil T/2 \rceil\) を正しく計算する必要があります。

アルゴリズム

以下の手順で解きます。

1. 全チームの募金総額 \(T\) を求める。
2. 目標金額 \(\lceil T/2 \rceil\) を計算する。整数演算では (total + 1) // 2 とすることで天井関数を実現できる。
3. 募金額を降順（大きい順）にソートする。
4. 大きい方から順に金額を足していき、累積和が目標金額以上になった時点での選んだチーム数を答えとする。

これは典型的な貪欲法（greedy algorithm）の考え方です。

(total + 1) // 2 が \(\lceil T/2 \rceil\) になる理由を確認しておきましょう。 - \(T\) が偶数（例: \(T=10\)）のとき → \((10+1)//2 = 5\) で \(\lceil 10/2 \rceil = 5\) に一致 - \(T\) が奇数（例: \(T=15\)）のとき → \((15+1)//2 = 8\) で \(\lceil 15/2 \rceil = 8\) に一致

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的。総和の計算と累積和は \(O(N)\)）
• 空間計算量: \(O(N)\)（入力配列の保持）

実装のポイント

• 入力の高速化: \(N\) が最大 \(10^6\) と大きいため、input() を繰り返し呼ぶと遅くなります。sys.stdin.buffer.read() でまとめて読み込み、一括で分割・変換することで高速化しています。

• 天井関数の扱い: 半分以上という条件は \(\lceil T/2 \rceil\) なので、(total + 1) // 2 と書くことで切り上げを実現します。total // 2 としてしまうと \(T\) が奇数のときに誤った答えになるため注意してください。

• 降順ソート: a.sort(reverse=True) で大きい順に並べ替えてから貪欲に足していきます。

• 必ず条件を満たせること: すべてのチームを選べば合計は \(T \geq \lceil T/2 \rceil\) となるため、ループ内で必ず条件が満たされ、答えが確定します。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(x) for x in data[1:1+n]]
    total = sum(a)
    half = (total + 1) // 2
    a.sort(reverse=True)
    s = 0
    cnt = 0
    for x in a:
        s += x
        cnt += 1
        if s >= half:
            break
    print(cnt)

main()

---

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