【Python3】【殿堂入りキャンペーン】お菓子の詰め合わせ (paizaランク A 相当)をやってみた

# utf-8
def combinations(iterable, r):
    # combinations()関数は、与えられたiterableからr個の要素を持つすべての組み合わせを生成するジェネレータです。
    pool = tuple(iterable)  # 入力のiterableをタプルに変換してpoolに格納します。
    n = len(pool)  # poolの長さ（要素の数）を取得します。
    if r > n:  # rがnより大きければ、組み合わせは存在しないので終了します。
        return
    indices = list(range(r))  # 組み合わせを表すインデックスのリストを作成します。
    yield tuple(pool[i] for i in indices)  # 最初の組み合わせを生成して返します。
    while True:
        for i in reversed(range(r)):  # 右端から左に向かってインデックスを調整します。
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1  # インデックスを調整します。
        for j in range(i + 1, r):  # 調整後のインデックスを更新します。
            indices[j] = indices[j - 1] + 1
        yield tuple(pool[i] for i in indices)  # 新しい組み合わせを生成して返します。

# 入力の受け取り
N, money = map(int, input().split())  # N: お菓子の種類数, money: 指定制限金額
All = []  # お菓子の値段リスト
for n in range(N):
    All.append(int(input()))  # 各お菓子の値段をリストに追加します。

All.sort()  # お菓子の値段リストを昇順にソートします。

# なるべく多くの種類を購入するための計算
temp = 0  # 合計金額の一時変数
count = 0  # 購入するお菓子の種類数
for i in All:
    temp += i  # お菓子の値段を加算します。
    if temp > money:  # 合計が指定制限金額を超えたらループを終了します。
        break
    count += 1  # 購入する種類数をインクリメントします。

temp = []  # 指定制限金額を超えない購入パターンの釣銭リスト
# 全ての組み合わせを生成して、釣銭を計算します。
for i in combinations(All, count):
    s = sum(i)  # 組み合わせの合計値を計算します。
    if s <= money:  # 指定制限金額を超えない場合
        temp.append(money - s)  # 釣銭をリストに追加します。

print(min(temp))  # 最小の釣銭を出力します。

解説

このプログラムは、指定された制限金額内でなるべく多くの種類のお菓子を購入し、その際の最小のお釣りを求めます。

1. combinations関数

   • 入力されたiterableからr個の要素を持つすべての組み合わせを生成するジェネレータ関数です。
   • poolに変換してから、indicesリストを使って組み合わせを生成します。
   • 右端から左に向かってインデックスを調整し、新しい組み合わせを生成します。

2. 入力の受け取り

   • N（お菓子の種類数）とmoney（指定制限金額）を受け取ります。
   • 続いて、各お菓子の値段をリストAllに追加します。

3. お菓子の値段リストのソート

   • 昇順にソートすることで、安い順にお菓子を選ぶことができます。

4. 種類の数を最大にするための計算

   • 変数tempに合計金額を一時的に保存し、countに購入するお菓子の種類数を保存します。
   • ループでお菓子の値段を加算し、指定制限金額を超えたら終了します。

5. 釣銭の計算

   • combinations関数を使用して、指定制限金額を超えない購入パターンのすべての組み合わせを生成します。
   • 各組み合わせの合計値が指定制限金額以下であれば、その釣銭をリストtempに追加します。

6. 最小の釣銭を出力

   • リストtempから最小の釣銭を見つけて出力します。

これにより、指定された制限金額内で最大の種類数のお菓子を購入し、最小のお釣りを得ることができます。