Pythonでbit全探索
●はじめに
以下の問題は複数の解き方が考えられると推測されますが、
今回はbit全探索の学習として紹介します。
より良い解法・考え方等ありましたら
知る事が出来ると嬉しい為、コメント頂ければ幸いです!
●更新の目安
(0)リンクで飛べるようにする・目次を作る
(1)この実装をしてみる
僕はbit全探索のときいつもこれ使ってます。
— グリ (@grigri_grin) 2020年5月24日
import itertools
n = 4#長さを指定
for i in itertools.product([0, 1], repeat=n):
print(i)
(2)All GreenとKadomatsuを解く
●bit全探索で解く事が可能な問題
(1)ABC045 C.たくさんの数式
(2)ABC079 C.Train Ticket
(3)ABC104 C.All Green
(4)ABC119 C.Synthetic Kadomatsu ※途中です!
(5)ABC128 C.Switches
(6)ABC147 C.HonestOrUnkind2
(7)ABC167 C.Skill Up
●ABC045 C.たくさんの数式
【問題概要】
文字列Sが与えられる。Sの文字と文字の間に"+"を入れることを考える。
全く"+"を入れない場合も考える。この時考え得る全ての数式から得られる
値の合計を出力。
【制約】
(1)1<=|S|<=10
(2)Sに含まれる文字は1~9までの数字
【考え方】
(1)ありうる全ての値の合計を求めたいのでans=0とする
(2)初期の数式として文字列Sの先頭の桁を設定する。
ここに以降の桁の数字をくっつける、または"+"を挿入して
最終的にその出来上がった数式をansに加算すると考える。
(3)全ての"+"の入れ方の組み合わせを考える。
この時の入れ方としてある桁が1であれば後ろに"+"を挿入
という方法を考える。
これはbit表記により実現できる。また与えられた文字列Sに対し先頭から
"+"を挿入するか否か見ていくことを考える為、最下位bitから見る事とする。
この時この組み合わせをqとする。
(4)このqに対してその桁が1であるならば"+"を挿入
そうでないならば以降の桁のうち先頭のものをくっつける
(5)(4)により出来た数式をansに加算して出力
【コード】
●ABC079 C.Train Ticket
【問題概要】
整数A,B,C,Dが与えられる。 A□B□C□D=7が成り立つように
□の中に"+","-"を入れた式を作り、その式を出力。
【制約】
(1)0<=A,B,C,D<=9
(2)与えられた入力に対して必ず答えは存在する
【考え方】
(1)□の数は3→"+","-"の入れ方は2**3=8通り
(2)考え得る"+","-"の入れ方をABC045Cの方法を真似て実装する。
ABC045Cと異なるのは必ず"+"または"-"を入れるという点
ある桁が1である場合は"+"を挿入、
ある桁が0である場合は"-"を挿入と考える
(3)出来た数式の答えが7となるならばその数式=7を出力。
【コード】
●ABC104 C.All Green
【問題概要】
1<=i<=D(i=1,2,3,...,D)のiに対して,100*i点の問題がpi個存在する事が
わかっている。各問題を解く事で100*iの点を得られるが、それとは別に
100*i点の問題の全て、すなわちpi個を解くことにより各コンプリートボーナスci点
を得ることができる。
この時点数の合計Gを達成するために必要な問題数の最小値を出力。
【制約】
(1)入力は全て整数
(2)1<=D<=10
(3)1<=pi<=100
(4)100<=ci<=10**6
(5)ci,Gは共に100の倍数である
(6)合計Gを達成する事は必ず可能である
【考え方】
(1)①pi問全て解く問題、
②一問も解かない問題、
③0より多くpi問より少なく解く問題
の三種類に分けると考える。
③に関しては①を除いた中で最も点数が高い物を選ぶ事とする
(2)(1)をbit全探索で実装するために桁が1になっている場合①、桁が0なら②とすると考える。この時問題があるのは③だが、これはリスト・bit表記を逆向きにし、bit表記で一番最初に0が出てきたら覚えておくことで実現できる。
(3)(2)に従い素直に実装を行う。①ならばボーナススコアも加算する。この時の一時的な合計<Gであり且つ③の範囲内で加算すればGを達成できるかどうかを確認する。もしそれができるのならば既存の解いた問題数cntと比較し、最小の解いた問題数であるならば更新する。
【コード】
●ABC119 C.Synthetic Kadomatsu
【問題概要】
N本の竹を持っており、各竹の長さはli (i=1,2,...,N)である。
この竹のうち何本かを選び、長さA,B,Cの3本の竹を作ることを考える。
竹に対しては以下3点の操作ができる。
(1)1MPを消費して1本選んだ竹に対してその長さを1プラスする
(2)1MPを消費して長さ2以上の選んだ竹の長さを1マイナスする
(3)10MPを消費して2本の竹を接続して1本の竹とする
この作成した1本の竹の長さは2本の竹の長さの合計と等しい
目的を達成するために必要なMPの最小値を出力。
【制約】
(1)入力は全て整数
(2)3<=N<=8
(3)1<=C<B<A<=1000
(4)1<=li<=1000
【考え方】
(1)
(2)
【コード】
●ABC128 C.Switches
【問題概要】
N個のスイッチとM個の電球がある。
スイッチはonとoffの二種類の状態を持つ。
電球i(i=1,2,...M)はki個のスイッチに
繋がっており、どのスイッチに繋がっているかはsij で与えられる。
この電球は、
(繋がっているスイッチのうちonになっている個数)%2=pi
である時点灯する。
全ての電球が点灯するようなスイッチのon/offの状態の組み合わせの個数を出力。
【制約】
(1)入力は全て整数
(2)1<=N,M<=10
(3)1<=ki<=N
(4)1<=sij<=N
(5)piは必ず0か1
【考え方】
(1)全ての電球が点灯するような組み合わせの個数を求めたいのでans=0とする
(2)全てのスイッチのon/offの組み合わせを考える
(3)全ての電球の点灯し具合を示すリストをlitとしておく
(4)電球のインデックスとその電球に接続するスイッチを見ていく
そのスイッチがonになっているならcntに加算
(5)cnt%2==p[電球のインデックス]ならばその電球は点灯
(6)全部点灯するならばansに加算して最終的なansを出力
【コード】
●ABC147 C.HonestOrUnkind2
【問題概要】
N人の人間がいて、彼らは"Honest"か"Unkind"に分類される。
Honestな人間は必ず正しい証言をする。
Unkindな人間は正しい証言も間違った証言もする。
人iはAi個の証言を行う。各証言は xij yij の形で与えられる。
これは"人xijはyij" という意味である。
(yij=1の時Honest、yij=0の時Unkind)
N人の中に最大で何人Honestな人間が存在するか出力。
【制約】
(1)1<=N<=15
(2)0<=Ai<=N-1
(3)1<=xij<=N
(4)自分についての証言はしない
(5)同じ人に対しての証言は各人1度のみ行う
【考え方】
(1)Honestな人間の最大値を求めたいのでans=0とする
(2)全ての組み合わせを考える。
この時矛盾するかしないかをflagという変数、
(今回はflag=1と初めに設定しておく)
Honestとなった人間のリストをhonest、
Unkindとなった人間のリストをunkindとしておく
(3)Honestな人間の証言が矛盾するケース1,ケース2を考える
ケース1:Honestな人間がある人物をHonestと答えたがその人物が
Unkindに分類されていた
ケース2:Honestな人間がある人物をUnkindと答えたがその人物が
Honestに分類されていた
ケース1,ケース2になった時はflag=0にする
(4)flag=1のままであるならば現在のhonestの人数をansと比較し
大きい方をansとして出力する
【コード】
●ABC167 C.Skill Up
【問題概要】
N個の参考書が売られており、各参考書の値段はCi円(i= 1,2,...,N )である。
各参考書を読むことにより、
M個ある能力がそれぞれAij上昇することが分かっている。
全ての能力をX以上にしたい時、それが達成不可能である場合は-1を、
達成可能である場合は達成が可能となる最小金額を出力。
【制約】
(1)入力は全て整数
(2)1<=N,M<=12
(3)1<=X<=10**5
(4)1<=Ci<=10**5
(5)0<=Aij<=10**5
【考え方】
(1)最小金額を求めたいので、minで更新できるようにans=float("inf")とする
(2)全ての組み合わせを試してみる
(3)その組み合わせを選択した場合の価格をpriceという変数,
その組み合わせを選択した場合の得られる能力のリストをabilとしておく
(4)購入したらpriceに加算、abilに得られる能力を加算
(5)実際に選択してみてそのabilの最小値>=Xとなったら目標が達成したという事
この時はans=min(ans,price)して更新
(6)ans=float("inf")のままだったら目標は達成できなかったという事
【コード】
zip演算