概要

\(N\) 種類のおやつから、それぞれ \(T\) 個ずつ購入する場合に、予算 \(E\) 円以内で最大何種類のおやつが買えるかを求める問題。

考察

この問題では、各おやつの合計価格 \(P_i \times T\) を考えた上で、できるだけ多くの種類のおやつを選ぶ必要があります。単純に全組み合わせを試すと、指数時間になってしまうため現実的ではありません（部分集合の数は \(2^N\) 通り）。

重要な観察として、「安いおやつから順に選んでいけば良い」という貪欲法の適用があります。なぜなら、目的が「種類数の最大化」なので、同じ予算でも安価なものを優先的に選ぶことで、より多くの種類を購入できる可能性が高くなるからです。

例えば、
- おやつの価格が \([3, 1, 2]\) 円で \(T = 2\)、予算 \(E = 6\) 円の場合、
- 各おやつの合計価格は \([6, 2, 4]\) 円となり、これをソートすると \([2, 4, 6]\)。
- この順に買っていくと、2種類までが可能で、最大種類数は 2 になります。

このように、価格の合計を前もって計算し、小さい順に選ぶことで最適解が得られます。

アルゴリズム

1. 各おやつの合計価格 \(P_i \times T\) を計算する。
2. 合計価格のリストを昇順にソートする。
3. ソートされた順におやつを買っていき、予算 \(E\) を超える直前までの個数をカウントする。

この貪欲法によって、最も多くの種類のおやつを選択できます。

計算量

• 時間計算量: \(O(N \log N)\)（ソートが支配的）
• 空間計算量: \(O(N)\)（合計価格を保存する配列）

実装のポイント

• 各おやつの合計価格 \(P_i \times T\) は事前に計算しておくと効率的。
• sort() を使って価格を昇順に並び替えることで、貪欲に選択できる。
• 入力を高速に読み込むことで、大きな \(N\) にも対応（Pythonの場合は sys.stdin.read などを使うと良い）。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    E = int(data[2])
    P = list(map(int, data[3:]))

    # 各おやつの合計価格を計算
    total_prices = [p * T for p in P]
    
    # 合計価格でソートして貪欲法を適用
    total_prices.sort()
    
    count = 0
    total_cost = 0
    
    for price in total_prices:
        if total_cost + price <= E:
            total_cost += price
            count += 1
        else:
            break
            
    print(count)

if __name__ == "__main__":
    main()

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