競プロ典型90問 016 - Minimum Coins（★3）コード解説

はじめに

もう12月の半ばです。12といえば…今週末のM1グランプリですね！

今年、個人的に目が離せないのはヨネダ2000です。結成して2年の女性コンビですが、ネタも振る舞いもとても若手とは思えないクオリティで、斬新すぎるネタは中毒性の塊です。（去年の敗者復活戦のネタを覚えている方もいるのでないでしょうか。）今週末を楽しみに木、金と乗り切っていきましょう！！

さて、今回は競プロ典型90問の★3問題を解説していきます！

競プロ典型90問

atcoder.jp

016 - Minimum Coins（★3）

016 - Minimum Coins（★3）

　

A円、B円、C円のコインがそれぞれ何枚かあり、それらの合計値がN円になるような組み合わせで、合計枚数が最も少ないものを出力します。

一番オーソドックスなものは、A円のところが10円、50円、100円のように具体的な金額が与えられていることが多いですが、これも同様です。

方針としてはそれぞれのコインの枚数に対して全探索を行い、合計がN円となるタイミングの枚数を記録して、最も少なくなる時の合計枚数を出力します。

愚直にコーディングした場合が以下になります。

n = int(input())
a, b, c = map(int, input().split(" "))

num_coins = n
for i in range(10000):
    for j in range(10000):
        for k in range(10000):
            if a*i + b*j + c*k == N:
                num = i+j+k
                if num < num_coins:
                    num_coins = num 
print(num_coins)

お察しの方もいらっしゃると思いますが、これはTLEとなります。

制約でコインの総数が9999以下ということはわかっているので、各コインについて10000通りの探索を行っていますが、3重ループなので必要な探索数は、(10⁴)³ = 10¹²となります。 1秒間に可能な計算回数の目安は1億回（10⁸）と言われているので、TLEとなるのも仕方がないといえます。

そこでループを減らす方法を考えましょう。
実はaの枚数とbの枚数が決まると、残りのcによってNが実現できるかどうかが決定します。 それは、
- N - (a(aの枚数) + b(bの枚数)) % c == 0
- N - (a(aの枚数) + b(bの枚数)) >= 0
の2つの条件によって判断できます。

これによって3重ループが2重ループで実現できるようになります。

n = int(input())
a, b, c = map(int, input().split(" "))

num_coins = n
for i in range(10000):
    for j in range(10000):
        if (n - (a*i + b*j)) % c == 0 and (n - (a*i + b*j)) >= 0:
            num = i + j + (n - (a*i + b*j)) // c
            if num_coins > num:
                num_coins = num
print(num_coins)

実はこのコード、Pythonで実行するとTLEになります。
え？さっき大丈夫って言ったじゃん！！嘘つき！！

安心してください、ACですよ。そうPyPyならね。
高速で動作するPyPy3で実行してみたらACしました。

おわりに

今回は計算量を削減するためにループを減らす問題でした。
かなり応用の効きそうな考え方なので、しっかり復讐しておきましょう。

お疲れ様でした。