読者です 読者をやめる 読者になる 読者になる

東大理三生のプログラミング奮闘記

初心者プログラマーが半年間でどれだけ成長するか!についてのブログです。勉強方法とか使った本とかについて書いていくと思います!プログラミングをもっと身近に感じてもらえたら嬉しいです!毎日更新を目指します!

ABC #054 D問題 を python で解いてみた!

python3

今日の晩の体操は AtCoder Biginner Contest の D 問題です。

問題はこちら↓
D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder

(解答)

from itertools import combinations

N,Ma,Mb = [int(n) for n in input().split()]
medicine_list = []
for i in range(N):
    medicine_list.append([int(n) for n in input().split()])

money_possible = []
counter = 0

for i in range(1, N+1):
    for medicine_comb in combinations(medicine_list, i):
        sum_a = 0
        sum_b = 0
        sum_c = 0
        for k in range(i):
            sum_a += medicine_comb[k][0]
            sum_b += medicine_comb[k][1]
            sum_c += medicine_comb[k][2]
        if sum_a/sum_b == Ma/Mb:
            money_possible.append(sum_c)

if len(money_possible) == 0:
    print(-1)
else:
    print(str(min(money_possible))+"円")


一応、AtCoderの検証例だとあっていることがわかります。(さすがに少なすぎませんか...)

f:id:gragragrao:20170301221435p:plain


5分強ぐらいで書けましたが、このコードには問題があると思います。

N が最大で 40 にまでなるので、for で回す回数が、約2の40乗回にまで膨れ上がります(二項定理より)。

これは、1099511627776回と、1兆回を超えます。

さらにこの中で i に対する for 文を回しているので、最大で800兆回( 40 × 40 ÷ 2 × 兆?)ぐらいの計算量になると思います。

これはpythonで処理できる範囲を超えているはずです。(Cとかならワンチャン??よくわかりません。)


ですが、この問題では「当てはまる組がなければ "-1" と表示しなければいけない」ので、全通りためさなくてはいけません。


「全通りためす」かつ「計算量を激減させる」方法を考える必要がありますが...どうやればいいんでしょうね〜思いつきません。



「こんな方法あるよ」とかあったら教えてください。

それでは〜