概要

予算 \(E\) 円以内で、各おやつを \(T\) 個ずつ買うという条件のもと、できるだけ多くの種類のおやつを買う問題です。貪欲法（グリーディ） で、安いおやつから順に選んでいけば最適解が得られます。

考察

重要な気づき

「種類数を最大化」したいので、1種類あたりのコストが小さいものから優先的に選ぶのが最善です。

おやつ \(i\) を買うときのコストは \(P_i \times T\) 円です。\(T\) はすべてのおやつで共通なので、値段 \(P_i\) が安いおやつほどコストが小さいことになります。

具体例

例えば \(N = 4\), \(T = 2\), \(E = 500\) で、値段が \(P = [100, 50, 200, 80]\) の場合を考えます。

• 値段を昇順にソートすると \([50, 80, 100, 200]\)
• 安い順に買っていくと：
  • \(50 \times 2 = 100\) 円（累計 \(100\) 円）→ 買える ✓
  • \(80 \times 2 = 160\) 円（累計 \(260\) 円）→ 買える ✓
  • \(100 \times 2 = 200\) 円（累計 \(460\) 円）→ 買える ✓
  • \(200 \times 2 = 400\) 円（累計 \(860\) 円）→ 予算オーバー ✗
• 答えは 3種類

なぜ貪欲法で正しいのか

種類数を最大化するには、限られた予算をできるだけ節約して多くの種類を詰め込む必要があります。安いものから選べば、同じ種類数を選ぶ場合の合計コストが最小になります。したがって、安い順に選ぶ貪欲法が最適です。

アルゴリズム

1. おやつの値段 \(P\) を昇順にソートする。
2. 安い方から順に \(P_i \times T\) を累計コストに加算していく。
3. 累計コストが予算 \(E\) を超えたら、そこで打ち切る。
4. それまでに選べたおやつの種類数が答え。

P をソート
total = 0, count = 0
for p in P:
    if total + p * T <= E:
        total += p * T
        count += 1
    else:
        break
出力: count

計算量

• 時間計算量: \(O(N \log N)\)（ソートがボトルネック。ループ部分は \(O(N)\)）
• 空間計算量: \(O(N)\)（値段の配列を保持）

実装のポイント

• オーバーフローに注意: \(P_i\) は最大 \(10^9\)、\(T\) は最大 \(10^4\) なので、\(P_i \times T\) は最大 \(10^{13}\) になります。また \(E\) は最大 \(10^{14}\) です。C++ などでは long long を使う必要がありますが、Python では整数の桁数に制限がないため、特別な対処は不要です。

• 早期打ち切り（break）: ソート済みの配列を安い順に見ているため、一度予算を超えたら、それ以降のおやつはさらに高価なので絶対に買えません。break で即座にループを抜けることで無駄な計算を省けます。

• 高速な入力: \(N\) が最大 \(10^5\) なので、Python では sys.stdin.read() を使ってまとめて読み込むと入力が高速になります。

  ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    T = int(input_data[1])
    E = int(input_data[2])
    P = [int(input_data[3 + i]) for i in range(N)]
    P.sort()
    total = 0
    count = 0
    for p in P:
        cost = p * T
        if total + cost <= E:
            total += cost
            count += 1
        else:
            break
    print(count)

main()

---

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