概要

\(N\) 個のチームの募金額から、全チームの募金総額の半分以上を集めるために必要な、最小のチーム数を求める問題です。

考察

• 素朴なアプローチの問題点: どのチームを選ぶかを全パターン試す（bit全探索など）と、計算量が \(O(2^N)\) となり、\(N \leq 10^6\) という制約では実行時間内に終わらずTLE（時間切れ）になってしまいます。
• 重要な観察: 「できるだけ少ないチーム数で目標額を達成する」という目的を考えると、1つのチームあたりが集める募金額が大きいほど有利です。したがって、募金額が大きいチームから順に選んでいくのが最適な選び方であると直感的に分かります。
• 貪欲法の正当性: もし「金額が大きいチームを選ばず、小さいチームを選んだ」という選び方をした場合、目標額に達するまでにより多くのチーム数を必要とするか、せいぜい同じチーム数にとどまります。したがって、金額が大きい順にソートして順番に足していく貪欲法を用いれば、必ず最小のチーム数を求めることができます。

アルゴリズム

1. 全チームの募金額の合計 \(T\) を計算します。
2. 表彰対象となるための目標額 \(\text{half} = \lceil T / 2 \rceil\) を計算します。\(T\) が奇数の場合も考慮し、整数の計算で切り上げを表すために (T + 1) / 2 とします。
3. 各チームの募金額 \(A_i\) を降順（大きい順）にソートします。
4. ソートされた配列を前から順に足し合わせていきます。
5. 合計が \(\text{half}\) 以上になった瞬間に処理を終了し、その時点までに選んだチーム数を出力します。

計算量

• 時間計算量: \(O(N \log N)\) （配列のソートがボトルネックになります）
• 空間計算量: \(O(N)\) （配列の保持に必要な領域です）

実装のポイント

• 募金額 \(A_i\) が最大 \(10^9\) であり、チーム数 \(N\) が最大 \(10^6\) のため、総額 \(T\) は最大 \(10^{15}\) になります。32ビット整数型（C++の int など）ではオーバーフローしてしまうため、64ビット整数型（long long など）を使用する必要があります。

• 目標額 \(\lceil T / 2 \rceil\) の計算は、T が奇数の場合に小数点以下を切り上げる必要がありますが、(T + 1) / 2 と記述することで整数の除算のみで正確に切り上げを表現できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    long long T = accumulate(A.begin(), A.end(), 0LL);
    long long half = (T + 1) / 2; // ceil(T / 2)
    
    sort(A.begin(), A.end(), greater<long long>());
    
    long long sum = 0;
    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        sum += A[i];
        cnt++;
        if (sum >= half) {
            break;
        }
    }
    
    cout << cnt << "\n";
    
    return 0;
}

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