ABC167 C問題(Bit全探索)
ABC167でBit全探索の問題をAC出来たので記事を書きました.
拙い記事ですが,勉強に役立ててもらえれば幸いです.
https://atcoder.jp/contests/abc167/tasks/abc167_c
考えたこと
N,Mの制約が「1<=N,M<=12」と非常に厳しい.
選択肢が「買う」or「買わない」という二択なのでnetでググりながらBit全探索というものを試みた.
実装
n, m, x=map(int, input().split())
book=[list(map(int, input().split())) for i in range(n)]###参考書の情報を受け取る.
costs=[]
for i in range(2**n):
t=[0]*m###m種類について「買う」or「買わない」の選択肢がある.
cost=0
for j in range(n):
if ((i>>j)&1)==1:###「1」→「買う」として買った参考書で各理解度が上昇!.
for k in range(m):
t[k]+=book[j][k+1]###先頭は参考書の値段であることに注意する.
cost+=book[j][0]
if all(t[l]>=x for l in range(m)):###全ての理解度がx以上であるときcostsに追加
costs.append(cost)
if len(costs)==0:###どの選び方でも目的を達成出来ない時
print(-1)
else:
print(min(costs))
終わりに
コンテスト中にAC出来て嬉しかったです.
今の僕の実力ではD問題でいつも弾かれているので,D問題が解けるようになりたいなぁ...