はいこんにちは!(^^)!
本日はAtCoder Beginners Selectionの第5問目、Coinsの解説をしていきたいと思います。少しづつ複雑になってきていますが、頑張っていきましょう。
Coins
【問題文】
あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。
【制約】
・0≦A,B,C≦50
・A+B+C≧1
・50≦X≦20000
・A,B,Cは整数である
・Xは50の倍数である
【入力】
A
B
C
X【出力】
硬貨を選ぶ方法の個数を出力せよ。
【入力例】
2
2
2
100【出力例】
2条件を満たす選び方は以下の2通りです。
・500円玉を0枚、100円玉を1枚、50円玉を0枚選ぶ。
・500円玉を0枚、100円玉を0枚、50円玉を2枚選ぶ。
どうでしょうか。どのように解けばよいかわかりますか？
この問題では、Xは50の倍数である、という制約がかかっていますね。AtCoderを解くときは、この制約を利用してコードを書くと、簡単なコードを書けることが多くあります。これからは、制約にも注目してみてくださいね。
それでは、解答例を見てみましょう。
【解答例】
A=int(input())
B=int(input())
C=int(input())
X=int(input())
count=0
for i in range(A+1):
for j in range(B+1):
I=i*500
J=j*100
if 0 <= X-I-J <= C*50:
count=1
print(count)では、このコードの解説をしていきます。
最初の4行では、キーボードから入力を受け取り、その値をint()によって数値型に変換していますね。これによって文字列として入力された値を数値として扱うことができます。
その次に、今回の最後に答えとして出力するcountを用意します（もちろん別の名前の変数でもOKです）。
ここからが少しややこしいところですね。
ここではfor~inの繰り返し構文を二重にして使っています。
まずはrange(A+1)で、500円玉の枚数として入力された値の数だけ0から順番に取り出していきます。
そのすぐ後にrange(B+1)によって100円玉の枚数として入力された値だけ0から順番に取り出します。
例えば500円玉が1枚、100円玉が2枚だとすると、
0 0
0 1
0 2
1 0
1 1
1 2
という風に取り出されることになります。
このようにして500円玉の枚数と100円玉の枚数を定めたら、それぞれに×500、×100をして、500円玉での金額と100円玉での金額を計算します。
そのあとのif文では、全体の金額から500円玉の金額と100円玉の金額を引き、残った金額が0から50円玉の金額の間にあるかどうかで条件分岐をしています。これがTRUEとなれば合計金額をちょうどX円にすることができたことになり、countに1を足すことになるのですが、この式は何を意味しているのでしょうか。
ここで、最初にあった「Xは50の倍数である」という制約を思い出してみましょう。X、つまり合計金額が50の倍数であるということは、合計金額から500円玉と100円玉の合計を引いた金額も、必ず50の倍数になるということです。50の倍数であれば、枚数さえ足りれば50円玉だけで表すことができますね。
したがって、全体の金額からその時選択した枚数の500円玉と100円玉の合計金額を引いた金額が、マイナスでもなく、50円の合計金額以下の場合、その金額は手持ちの硬貨で表すことができるということです。
終わりに
今回の問題では、難しい関数が出てきたわけではないですが、forを使った二重ループの式が出てきました。この二重ループについて書いている記事もありますので、良ければこちらもご覧ください！
それでは、また次の問題でお会いしましょう(^^)/
次の記事