TOYPRO解説記事 - 枚数(200点)

1 min read読了の目安(約1200字

1.概要

競技プログラミングのサイト「TOYPRO」の200点問題、枚数の解説をします!

2.問題

5円玉と7円玉がそれぞれ十分にあります。
これらを好きなだけ選んで合計をちょうどn円にする方法が何通りあるか出力してください。
ただし、どちらの硬貨も一枚以上選ぶこと。

制約

n <= 1000000

必要な変数

n

入力例

n = 12

出力例

1

TOYPROの方の問題文が間違っているので現在修正をお願いしています

3.解説

3-1.誤答例

まず、5円玉と7円玉の枚数を全探索する方法が考えられます。
これを実装すると次のようなコードになります。

n=12
ans=0
for i in range(1,n//5+1):
    for j in range(1,n//7+1):
        if i*5+j*7==n:
            ans+=1
print(ans)

ところで、TOYPROでは5秒間で処理が打ち切られ、その間でコンピューターが計算できる回数は高々10^{8}程度であるということが知られています。
しかし、nが最も大きい1000000であった場合、(1000000/5)*(1000000/7)より、だいたい3*10^{10}回の計算をしなければならないことになります。
これは明らかに計算回数が多すぎるため、処理が打ち切られてしまうわけです。

3-2.想定解

5円玉の枚数で7円玉の枚数を表すことを考えます。
5円玉の枚数をi枚、7円玉の枚数をj枚とすると次のような式を立てることができます。

5*i+7*j=n

これを式変形します。

7*j=n-5*i

j=\cfrac{n-5*i}{7}

この式を利用することにより、nが最も大きい1000000であった場合にも1000000/7(≒142857)回程度の計算回数で解を求めることができます。
どちらも1枚以上選ばなければならないことに注意して実装すると、解答は次のようなコードになります。

n=12
ans=0
for i in range(1,n//5):
    if (n-i*5)%7==0:
        ans+=1
print(ans)

j、つまり7円玉の枚数が整数であれば条件を満たす選びかたの一つとしてカウントしています。

4.おわりに

この記事を読んでくださりありがとうございます!
自分にとって初めての記事だったので難しかったです;;
TOYPROには他にも面白い問題がたくさんあるのでぜひご利用ください!

https://www.toy-pro.net/