概要

与えられたお菓子の個数 \(P\) で、なるべく多くの子どもを満足させる（必要なお菓子を全部配る）問題です。

考察

この問題では、各子ども \(i\) に対して「\(S_i\) 個のお菓子が必要」という条件があります。
満足させるためには、その子に必要な個数を全て渡さなくてはいけません。

素朴な方法として、「貪欲に少ない順に配っていけばいいのでは？」と考えられます。
つまり、\(S_i\) を昇順に並べて、前から合計が \(P\) を超えない範囲で取っていけばよいです。

しかし、例えば子どもが10万人いる場合、全員のお菓子の必要数が1億で、合計が100億を超えるケースでは、普通にループすると時間がかかりすぎます（TLE）。
そこで、累積和を使って「最初の \(k\) 人を満足させるのに必要なお菓子の合計」を高速に求め、さらに二分探索によって「最大何人まで満足させられるか」を探します。

このように、単純なループではなく、ソート＋累積和＋二分探索という典型的なテクニックを組み合わせることで効率的に解けます。

アルゴリズム

1. 各子どもが必要とするお菓子の個数 \(S_i\) を昇順にソートします。
2. ソートした配列の累積和を前もって計算しておきます。これにより、最初の \(k\) 人の子どもを満足させるのに必要な合計個数を \(O(1)\) で取得できます。
3. 「何人まで満足させられるか？」を二分探索で求めます：
   • cumsum[k] <= P であれば、\(k\) 人は満足可能なので、答え候補を更新し、さらに人数を増やせるか調べます（left = mid + 1）。
   • cumsum[k] > P なら、\(k\) 人は満足させられないため、人数を減らします（right = mid - 1）。
4. 探索終了後に得られた最大人数を出力します。

例

入力:

5 10
3 1 4 2 5

• ソート後: [1, 2, 3, 4, 5]
• 累積和: [0, 1, 3, 6, 10, 15]
• 二分探索で cumsum[4] = 10 <= 10 → 最大4人まで満足可能

出力: 4

計算量

• 時間計算量: \(O(N \log N)\) （ソートと二分探索）
• 空間計算量: \(O(N)\) （累積和配列）

実装のポイント

• 累積和を事前に計算しておくことで、区間和を高速に求められる。
• 二分探索の範囲は 0 から N まで。
• Pythonでは sys.stdin.read を使うことで大量の入力を高速に読み込めます。

## ソースコード

```python
import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = int(data[1])
    S = list(map(int, data[2:]))

    # 昇順にソート
    S.sort()
    
    # 累積和を計算
    cumsum = [0] * (N + 1)
    for i in range(N):
        cumsum[i + 1] = cumsum[i] + S[i]
    
    # 満足できる最大人数を二分探索
    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if cumsum[mid] <= P:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    
    print(answer)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。