ABC168 C問題[bit全探索]

C - Skill Up

要約

C_n円の本がN冊あって，各本について読めばM個の能力がA_nm上がっていき，一番安い値段で，すべての能力がXを超す時の値段を求める問題．

直近のABCの問題でこのような条件から3個選んで．．って問題は二分探索を使って解いていたのでそのように解くかと考えていたら，N,Mは共に最大12なので，各本の買い方は最大で2^12 = 4096 = O(10^3)なので全パターン考えても余裕な事に気づく．また，本の買い方を決めた後，M個の能力を考えようとpythonではM個の要素を探索するとO(M)になるので，最大計算量はO(M*10^3) ~O(10^4)となり，特に実装は気にしなくて良いことが分かる．

N, M, X = map(int, input().split())
C=[]
A = []
for i in range(N):
 x = list(map(int, input().split()))
 C.append(x[0])
 A.append(x[1:])


from itertools import product
ans = 10**10
#bit[i]がTrueならi番目の商品を買う
for bit in product((True, False), repeat=N):
 price = 0
 alg = [0]*M
 for i in range(N):
   if bit[i]:
     price += C[i]
     for j in range(M):
       alg[j] += A[i][j]
 #print(bit, price)
 if all([j >= X for j in alg]):
   ans = min(ans, price)
if ans == 10**10:
 print(-1)
else:
 print(ans)
     

各本の買い方についてbit全探索していく．

bit[i]がTrueならi番目の本を買う．

例えば(True, True, False)なら1冊目．2冊目の本は買って，3冊目は買わないということだ．あとは，i番目の本を買うときにはその値段を足して，能力を足してシミュレーションして行けばOK

感想

C埋めをしていく中でだいぶbit全探索の問題を解いてきたこともあり，解き方に気づいてから実装にかかる時間はだいぶ短くなっていて嬉しい．