【ABC167 C問題】bit全探索のやり方とサンプルコード【python3】

概要

競技プログラミングである「AtCoder Biginner Contest」の第167回C問題．

「Skill Up」 (引用：https://atcoder.jp/contests/abc167/tasks/abc167_c)

を解いてみた．

この問題では，組み合わせを全通り探索しなくてはいけなかったので，

「ビット全探索」

という手法を用いた．

ビット全探索って？

組み合わせを全探索する手法の一つ．

例題でいうと，

「100円のドリンクA，200円のドリンクB，300円のドリンクC，400円のドリンクDが売られていたとき，買い合わせのパターンを全て列挙せよ」

という問題があったとする．

全ての組み合わせを列挙すると，

[(A)，(B)，(C)，(D)，(A,B)，(A,C)，(A,D)，(A,B,C)，．．．]

という風になる．これをプログラムで処理したい時に「ビット全探索」が役に立つ．

まず列挙数について，これは「A,B,C,D」を買うor買わない，つまり1or0で判断できるため，列挙数は2*2*2*2で16通りとなる．

これをうまく利用して探索するのがビット探索．

ソースコード

drinks=[[A,100],[B,200],[C,300],[D,400]]
n=len(drinks)
for i in range(n): #ビット全探索
　　　bag=[]
　　　for j in range(n)
　　　　　　if (i>>j) & 1:
　　　　　　　　　bag.append(drinks[j])
　　　print(bag)

ビット探索は3~7行目．

6行目ではシフト演算を行って，iを2進数表現した後，そのiに含まれる1の位置を見つけている．もし「i=5」であれば，2進数表現すると「0101」になり，1の位置は右から1つ目と3つ目．この時，drinks[0]とdrinks[2]を配列bagに追加し，これを組み合わせのパターンとして出力している．

ABC167 C問題「Skill Up」

ソースコード

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n,m,x=input2()
CA=[]
ans=10**9

for _ in range(n):
	CA.append(input_array())

# ビット全探索
for i in range(2**n):
	bag=[]
	for j in range(n): #ビット全探索
		if (i>>j) & 1:
			bag.append(CA[j])
	enoughs=[0]*m #スキルがx以上身に付く数
	skills=[0]*m #身に付くスキルの合計
	money=0 #探索中の金額

	for b in bag:
		money+=b[0]
		for k in range(1,m+1):
			skills[k-1]+=b[k]
			if skills[k-1]>=x:
				enoughs[k-1]+=1
	if 0 not in enoughs: #全てのスキルが身についた時
		if money<ans:
			ans=money #価格の更新
if ans==10**9:
	print(-1)
else:
	print(ans)

ビット全探索で全て列挙し，全ての組み合わせに対してスキルが身についたか(x以上か)を判定する．