概要

各おやつを必ず \(T\) 個ずつ買うとき、予算 \(E\) 円以内で買える「おやつの種類数」の最大値を求めます。結論として、安いおやつから順に選ぶ貪欲法で最大化できます。

考察

重要な気づき

おやつ \(i\) を選ぶと必ず \(P_i \times T\) 円かかります。したがって条件は
\(\displaystyle \sum_{i \in S} (P_i \times T) \le E\)
です。

ここで \(T\) は全ての種類で共通なので、両辺を \(T\) で割る発想が有効です。
\(\displaystyle \sum_{i \in S} P_i \le \left\lfloor \frac{E}{T} \right\rfloor\)
となり、「値段 \(P_i\) の品物をいくつか選び、合計がある上限以内になるようにしたとき、何個（何種類）選べるか」という問題に変形できます。

なぜ安い順が最適か

「種類数」を最大化したいので、同じ予算なら 1 種類あたりのコストが小さいものを優先すべきです。

たとえば、残り予算が限られているときに高いおやつを選んでしまうと、そのせいで複数の安いおやつが買えなくなる可能性があります。
逆に、常に安い順に選べば、同じ予算で選べる種類数が最も多くなります（典型的な「合計制約下で個数最大化」問題で、重みが正のときは昇順に詰めるのが最適）。

素朴なアプローチが危険な理由

• 全ての部分集合を試す方法は \(2^N\) 通りで、\(N \le 10^5\) では不可能です。
• 「どの組合せが良いか」を DP（ナップサック）で解くのも、予算 \(E\) が最大 \(10^{14}\) と巨大で現実的ではありません。

そこで、「\(T\) が共通」な点を使って簡約し、さらに貪欲法に落とし込みます。

アルゴリズム

1. \(P\) を昇順にソートする。
2. 予算を \(T\) 個分で割った上限 \(budget = \left\lfloor \frac{E}{T} \right\rfloor\) を計算する。
   このとき「選んだおやつの \(P_i\) の合計が \(budget\) 以下なら、元の条件も必ず満たす」。
3. 小さい \(P_i\) から順に見ていき、現在の合計 \(s\) に足しても \(s + P_i \le budget\) なら採用する。
4. これ以上採用できなくなった時点で終了し、採用数を答える。

例：\(T=3, E=20, P=[4,2,5,1]\) のとき
\(budget=\lfloor 20/3 \rfloor=6\)、\(P\) をソートして \([1,2,4,5]\)。
\(1+2=3\) までは入るが、次の \(4\) を足すと \(7>6\) なので終了。答えは \(2\) 種類。

計算量

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

実装のポイント

• \(E\) は最大 \(10^{14}\) なので、言語によっては 64bit 整数が必須です（Python は自動で大丈夫）。

• \(\sum P_i \times T \le E\) を直接計算してもよいですが、先に \(budget = E // T\) にして \(\sum P_i \le budget\) とする方が安全・簡潔です。

• ソート後は「これ以上入らない」時点で以降も入らないため、ループを break して高速化できます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, T, E = data[0], data[1], data[2]
    P = data[3:3 + N]

    P.sort()
    budget = E // T  # sum(P_i) <= floor(E / T)

    s = 0
    ans = 0
    for p in P:
        if s + p <= budget:
            s += p
            ans += 1
        else:
            break

    print(ans)

if __name__ == "__main__":
    main()

---

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