概要

この問題は、与えられた \(N\) 個のチームの募金額からいくつかを選び、その合計が全体の半分以上（ \(\lceil T / 2 \rceil\) 以上）となるような最小のチーム数を求める問題です。

考察

重要な気づき

選ぶチームの数を最小限に抑えるためには、「募金額が多いチームから優先的に選ぶ」というアプローチ（貪欲法）が最適です。

例えば、募金額が \([10, 20, 30, 40]\) の 4 チームがある場合を考えます。総額は \(100\) なので、目標値は \(50\) です。 - 小さい順に選ぶ場合：\(10 + 20 + 30 = 60\)（3チーム必要） - 大きい順に選ぶ場合：\(40 + 30 = 70\)（2チームで達成）

このように、1回あたりの選択でできるだけ多くの募金額を回収するために、金額の大きいチームから順に選んでいくのが最も効率的です。

解決策

1. すべてのチームの募金額の総和 \(T\) を求め、目標値 \(\lceil T / 2 \rceil\) を計算します。
2. 募金額の配列 \(A\) を降順（大きい順）にソートします。
3. 先頭（募金額が最も多いチーム）から順に募金額を足し合わせていき、合計が目標値以上になった時点で終了します。その時までに選んだチームの数が答えとなります。

アルゴリズム

1. 入力を受け取りながら、募金額の総和 total_sum を計算します。
2. 目標値を target = (total_sum + 1) / 2 として計算します（これは \(\lceil T / 2 \rceil\) の整数計算による表現です）。
3. 配列 \(A\) を降順にソートします。
4. ループを回して大きい順に値を累積していき、累積和が target 以上になった瞬間のループ回数（選んだチーム数）を出力して終了します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 募金額の総和の計算および累積和の走査には \(O(N)\) の時間がかかります。
  • ボトルネックとなるのは配列のソートであり、これに \(O(N \log N)\) の時間がかかります。 \(N \le 10^6\) であるため、実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\)
  • 入力された募金額を保持するためにサイズ \(N\) の配列（std::vector）を使用します。

実装のポイント

• オーバーフローの防止: \(N\) は最大で \(10^6\)、各 \(A_i\) は最大で \(10^9\) であるため、募金総額 \(T\) は最大で \(10^{15}\) に達します。これは標準的な32ビット整数型（C++の int）の最大値（約 \(2 \times 10^9\)）を大きく超えるため、必ず64ビット整数型（C++の long long）を使用する必要があります。

• 切り上げ処理: 総和 \(T\) の半分以上（切り上げ）を求める際、浮動小数点数（double など）を使うと誤差の原因になります。整数型の演算のみを用いて (total_sum + 1) / 2 と計算することで、安全かつ正確に切り上げ値を求めることができます。

• 入出力の高速化: \(N = 10^6\) と入力の数が非常に多いため、C++では cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて入出力を高速化しておくことで、実行時間を大幅に短縮できます。

  ソースコード

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    if (!(cin >> N)) return 0;

    vector<long long> A(N);
    long long total_sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        total_sum += A[i];
    }

    sort(A.rbegin(), A.rend());

    long long target = (total_sum + 1) / 2;
    long long current_sum = 0;
    int count = 0;

    for (int i = 0; i < N; ++i) {
        current_sum += A[i];
        count++;
        if (current_sum >= target) {
            break;
        }
    }

    cout << count << "\n";

    return 0;
}

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