PythonでN種類すべてのキャンディを購入する際の最小金額と最大金額を求める方法

問題の概要

あるお菓子屋さんでは、N種類のキャンディが販売されており、それぞれの価格が与えられています。この店では魅力的なキャンペーンを実施していて、キャンディを1つ購入すると、別の種類のキャンディを最大K個まで無料でもらえるというオファーがあります。

今回の課題は、N種類すべてのキャンディを買い揃えるために必要となる最小の支払金額と最大の支払金額をそれぞれ求めることです。どちらの場合も、必ずこのオファーを活用して、できるだけ多くのキャンディを無料で手に入れるものとします。残っているキャンディがK個以上ある場合は、1つ購入するごとに必ずK個を受け取ります。K個未満しか残っていない場合は、残りをすべて無料でもらうことになります。

具体例

例として、price = [4, 3, 2, 5]、k = 2 という入力を考えてみましょう。この場合の出力は「最小 = 5」「最大 = 9」になります。

k = 2 のとき、キャンディを1つ買うたびに、さらに2つまで無料でもらえます。

• 最小金額の場合： 最も安い2円のキャンディを購入し、4円と5円のキャンディを無料でもらいます。その後、3円のキャンディを購入すれば全種類がそろいます。したがって最小コストは 2 + 3 = 5 となります。
• 最大金額の場合： 最も高い5円のキャンディを購入し、2円と3円のキャンディを無料でもらいます。その後、4円のキャンディを購入します。したがって最大コストは 4 + 5 = 9 となります。

解決のためのアルゴリズム

この問題は貪欲法（グリーディ法）を使えば効率よく解けます。手順は以下のとおりです。

1. 関数 get_min() を定義します。引数としてリストAとkを受け取ります。
2. n := Aのサイズとし、リストAを昇順にソートします。
3. res := 0、i := 0 と初期化します。
4. n が0になるまで以下を繰り返します。
   　・res := res + A[i]
   　・n := n − k
   　・i := i + 1
5. res を返します。
6. 関数 get_max() を定義します。引数は同様にAとkです。
7. n := Aのサイズ、リストAをソート、res := 0、idx := 0 とし、i := n − 1 から開始します。
8. i >= idx である間、以下を繰り返します。
   　・res := res + A[i]
   　・idx := idx + k
   　・i := i − 1
9. res を返します。
10. メイン処理から get_min(A, k) と get_max(A, k) を呼び出して結果を取得します。

ポイントは、最小金額を求めるときは安い順に購入して高価なキャンディを無料でもらい、最大金額を求めるときは高い順に購入して安いキャンディを無料でもらう点です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def get_min(A, k):
    n = len(A)
    A.sort()
    res = 0
    i = 0
    while(n):
        res += A[i]
        n = n - k
        i += 1
    return res

def get_max(A, k):
    n = len(A)
    A.sort()
    res = 0
    idx = 0
    i = n - 1
    while(i >= idx):
        res += A[i]
        idx += k
        i -= 1
    return res

A = [4, 3, 2, 5]
k = 2
print(get_min(A, k), get_max(A, k))

入力

[4, 3, 2, 5], 2

出力

5 9

まとめ

最小金額は昇順ソートしたリストの先頭から、最大金額は末尾から購入していくことで、シンプルなループだけで答えを導き出せます。計算量はソート部分が支配的となり、全体でO(N log N)です。このように貪欲法を活用すると、「1つ買うとK個無料」のようなプロモーション問題を効率的に解くことができます。