概要

各子どもが満足するのに必要なお菓子数 \(S_i\) が与えられるとき、合計 \(P\) 個以内で「満足させられる子どもの人数」を最大化します。

考察

重要な観察は、「人数を最大化したいなら、必要数が少ない子から満足させるのが最適」ということです。

• 1人を満足させるには、その子に \(S_i\) 個を“全部”渡す必要があります（途中まで渡しても無意味）。
• したがって、限られた予算 \(P\) の中で“できるだけ多く”の人数を取るには、コスト（必要個数）が小さいものを優先するのが自然です。

具体例： - \(P=10\), \(S=[6,6,2,2]\) のとき
大きい順に選ぶと \(6+6=12\) で 1人もしくは 1人しか満足できません。
小さい順に選ぶと \(2+2+6=10\) で 3人満足できます。

素朴に「満足させる子の集合を全探索」すると、組合せが \(2^N\) 通りあり \(N \le 2\times 10^5\) では到底不可能です（TLE）。
この問題は「小さい順に貪欲に取る」だけで最適解が得られます。

なぜ貪欲が正しいか（直感）： - ある解で、必要数が大きい子を選んでいて、選んでいない子にそれより小さい必要数の子がいるなら、入れ替えることで合計使用数を減らせます（人数は維持）。
- 合計を減らせれば、さらに別の子を追加できる可能性が増え、人数最大化に有利です。
- よって「必要数が小さい子から詰める」形が最適になります。

アルゴリズム

1. 配列 \(S\) を昇順にソートする。
2. 小さい順に見ていき、累積和 total に \(S_i\) を足しても \(P\) を超えない限り採用する。
3. 途中で total + S_i > P になったら、それ以降は必要数がさらに大きいので絶対に採用できず、打ち切ってよい。
4. 採用できた人数を出力する。

計算量

• 時間計算量: ソートが支配的で \(O(N \log N)\)
• 空間計算量: 配列保持などで \(O(N)\)

実装のポイント

• \(P \le 10^{18}\) なので、累積和 total は大きくなります。Python なら多倍長整数で安全ですが、他言語では long long 相当を使います。

• ソート後に total + x > P となった時点で break できるのが重要です（以降も不可能）。

• 入力サイズが大きいので、Python では sys.stdin.readline を使うと安定します。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = list(map(int, input().split()))
    S.sort()
    total = 0
    ans = 0
    for x in S:
        if total + x > P:
            break
        total += x
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。