三井住友信託銀行プログラミングコンテスト2019　100 to 105 python 3

2020/7/5 競技プログラミング

問題：https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_c

コード例

X=int(input())
maisu_max=X//100
if X<100:
    print(0)
    exit()
else:
    X=str(X)
    X=int(X[-2:])
    if X==0:
        print(1)
        exit()
ans=100
for i in range(2):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for m in range(20):
                    tmp=i+j*2+k*3+l*4+m*5
                    if tmp==X:
                        if i+j+k+l+m<ans:
                            ans=i+j+k+l+m
if maisu_max>=ans:
    print(1)
else:
    print(0)

for文で全探索だが、硬貨の種類が6種類ある。Xの最大が100000のため硬貨の枚数は最大1000(=10^3)。これをまともに6重ループで回すと計算量が10^18回となってしまい間に合わない。なので工夫が必要である。

まず、Xが100より小さい場合は問答無用でNGである。次にXが100の倍数の場合は問答無用でOKである。

続いてそれ以外のケースについて以下のように考える。まずXを100で割ると、その買い物で買える物の最大の個数が求まる。上のコードだと「maisu_max」に入っている。

Xの下二桁に着目する。下二桁を各買い物の下一桁を使って再現するために必要な最低の買い物個数を全探索で求める。サンプル1の615円で言えば下２桁の「15円」をどのように再現できるか。この場合、105円のパソコンを３個買うのが最小の組み合わせだ。これが「maisu_max」以下ならば、あとの買い物は合計金額がXになるまで100円のおにぎりを買い足せば条件を満たせる。「maisu_max」は6なのでこれはOK。

サンプル2の217円の場合は、買える物の個数は最大２個。17円を構成するために必要な最小パターンは5円*3と2円*1で合計4個。買える物の個数が最大２個なのでこれは条件を満たさずNGとなる。

という感じでAC。

Xの下二桁の取得は、一旦文字列に変換してから、スライスで下二桁を取り出して再度intに変換して行った。

コード例

関連