概要

限られた個数のお菓子を使って、できるだけ多くの子どもを満足させる問題です。これは典型的な貪欲法で解くことができます。

考察

重要な気づき

満足させる子どもの人数を最大化したいので、できるだけ少ないお菓子で多くの子どもを満足させる必要があります。

例えば、\(P = 10\) 個のお菓子があり、3人の子どもがそれぞれ \(S = [7, 2, 3]\) 個のお菓子を必要としている場合を考えます。

• 7個必要な子どもに配ると、残り3個で、もう1人（3個必要な子）だけ満足させられる → 2人
• 2個と3個必要な子どもに配ると、合計5個使い、残り5個 → 2人（7個必要な子は満足させられない）

この例では同じですが、必要な個数が少ない子どもから配った方が、より多くの子どもを満足させやすいことが直感的にわかります。

なぜ貪欲法が最適か

必要なお菓子の個数が少ない子どもから順に配っていく貪欲法が最適である理由：

• 「少ない個数で満足する子ども」を満足させても、「多い個数で満足する子ども」を満足させる余地は残る
• 逆に「多い個数で満足する子ども」を先に満足させると、お菓子をたくさん消費してしまい、満足させられる人数が減る可能性がある

つまり、小さい \(S_i\) の子どもから順に配ることで、同じお菓子の量でより多くの子どもを満足させられます。

アルゴリズム

1. 各子どもが必要とするお菓子の個数 \(S\) を昇順にソートする
2. ソートした順に、お菓子を配っていく
3. 累計がお菓子の総数 \(P\) を超えない限り、子どもを満足させ続ける
4. \(P\) を超えたら終了し、それまでに満足させた人数を出力する

具体例

\(N = 4, P = 10, S = [5, 1, 3, 2]\) の場合：

1. ソート後: \(S = [1, 2, 3, 5]\)
2. 1個必要な子ども → 累計 \(1 \leq 10\) → 満足（1人目）
3. 2個必要な子ども → 累計 \(1 + 2 = 3 \leq 10\) → 満足（2人目）
4. 3個必要な子ども → 累計 \(3 + 3 = 6 \leq 10\) → 満足（3人目）
5. 5個必要な子ども → 累計 \(6 + 5 = 11 > 10\) → 満足させられない

答え: 3人

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • その後のループは \(O(N)\)
• 空間計算量: \(O(N)\)
  • 配列 \(S\) の格納に必要

実装のポイント

• \(P\) が最大 \(10^{18}\) と非常に大きいため、累計を計算する変数はオーバーフローに注意（Pythonでは自動で多倍長整数になるため問題なし）

• 一度 \(P\) を超えたら、それ以降の子どもは全員満足させられないので、ループを break で抜けて効率化できる

• ソートは昇順（小さい順）であることを確認する

  ソースコード

def solve():
    N, P = map(int, input().split())
    S = list(map(int, input().split()))
    
    # 貪欲法：満足させる人数を最大化するには、必要なお菓子の少ない子どもから順に配る
    S.sort()
    
    total = 0
    count = 0
    
    for s in S:
        if total + s <= P:
            total += s
            count += 1
        else:
            break
    
    print(count)

solve()

---

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