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

AtCoder
この記事は約4分で読めます。
スポンサーリンク

概要

競技プログラミングである「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以上か)を判定する.

参考

大変お世話になりました.

Python de アルゴリズム(bit全探索) - Qiita
bit全探索とは 「n 個の選択肢それぞれに Yes or No の二択があるが、その部分集合(選択できるパターン)の全てを網羅的にチェックしたい」といった場合に使えます。Yes or No の二択が n 箇所あるので、パターン...
Atcoder ABC167 A-DをPythonで - Qiita
A. Registration 新しいidの$|S|-1$文字目までが同じであればYes、そうでなければNoを出力 ABC167a.py a=input() b=input() s=len(a) if b!=a: ...

コメント

タイトルとURLをコピーしました