概要

予算 \(E\) 円以内で、それぞれのおやつを \(T\) 個ずつ買うとき、最大で何種類のおやつを買えるかを求める問題です。

考察

各おやつ \(i\) を買う場合、\(T\) 個買う必要があるため、必要な金額は \(P_i \times T\) 円です。問題は、これらの合計が \(E\) 以下になるようにおやつの種類を選ぶとき、選べる種類数の最大値を求めることです。

これは典型的な「貪欲法」が適用できる問題です。合計金額を最小化しながら多くの種類を選ぶには、1種類あたりのコストが小さいものから順に選んでいくのが最適です。なぜなら、コストが小さいものほど予算を節約でき、より多くの種類を選ぶ余地が生まれるからです。

アルゴリズム

1. 各おやつ \(i\) について、\(T\) 個買うときのコスト \(P_i \times T\) を計算します
2. これらのコストを小さい順にソートします
3. ソートされたリストを先頭から順に見ていき、予算 \(E\) を超えない限りコストを合計に加えていきます
4. 追加できたアイテムの数が答えとなります

この貪欲法が最適解を与える理由は、コストが小さいものから選ぶことで、同じ予算で最大数のアイテムを選べるからです。

計算量

• 時間計算量: \(O(N \log N)\)
  • コストのリストをソートする処理が支配的です
  • その後の貪欲な選択は \(O(N)\) で実行できます
• 空間計算量: \(O(N)\)
  • コストのリストを保持するためのメモリが必要です

実装のポイント

• 各おやつのコストを \(P_i \times T\) で計算する際、整数の乗算なのでオーバーフローに注意が必要ですが、Pythonでは自動で多倍長整数が扱われるため問題ありません

• ソート後に小さい順に選択する単純なループで実装できます

• 予算 \(E\) が最大 \(10^{14}\) と大きいため、整数演算で正確に処理する必要があります

  ソースコード

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    T = int(data[1])
    E_val = int(data[2])
    P_list = list(map(int, data[3:3+n]))
    
    total_cost_per_item = [p * T for p in P_list]
    total_cost_per_item.sort()
    
    count = 0
    current_sum = 0
    for cost in total_cost_per_item:
        if current_sum + cost <= E_val:
            current_sum += cost
            count += 1
        else:
            break
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。