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

今日の晩の体操は 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の検証例だとあっていることがわかります。（さすがに少なすぎませんか...）

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

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

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

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

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

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

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

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

それでは〜