この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185
前：https://qiita.com/sano192/items/1b0c9f6a0794e5595ef0
【目標】
・Bit全探索を実装できるようになる
【概要】
Bit全探索というテクニックを使って解く問題。Bit全探索は非常によく出題されるテーマなのだが実装はなかなか難しい。しかし書き方のパターンは決まっているのでひとつできるようになればBit全探索の問題が「カモ」になる。この問題で実装まで完璧にできるようになろう。
【方針】
一見すると複雑な問題に見えるが制約が1<=N,M<=12と非常に小さい。
各参考書については買うか、買わないかの二択なので全パターンを試しても2^12=4096パターンしかない。そのため、全パターンを試して理解度がX以上になったもののうち、金額が最小のものを確認すれば良い。
二択のパターンをすべて試すにはBit全探索というテクニックを使う。
Bit全探索は2進数を使って全探索を行うテクニック。
それぞれの参考書について、0なら買わない、1なら買う、と2進数で対応づけを行っていく。
例としてN=8、つまり8冊の参考書がある場合を考える。
最初の参考書を「0冊目」とし、
「0冊目」、「4冊目」、「6冊目」
を買うパターンは2進数で表すと
01010001
となる。
右から0桁目、4桁目、6桁目が1になっているから「0冊目」、「4冊目」、「6冊目」を買うということを表している。
(左から、ではなく右から、であることに注意)
以上のように対応付けを考え
00000000～11111111
まで探索すれば全てのパターンを網羅できる。
次に実装で必要になる部分を説明しよう。
上記のように2進数で買う、買わないを管理する場合、どの桁が1となっているか？という情報を確認しなければならない。
そのために
「シフト演算」
「アンド演算」
というbit演算を使う。
「シフト演算」
シフト演算は2進数を左右にずらす演算。
たとえば
01010001
を右に2つシフト演算すると
00010100
となる。
(01010001を右に2つ動かすと右端の01はなくなり、左端に00が増える)
もうひとつ例を見よう。
11111111
を右に2つシフト演算すると
00111111
となる。
(11111111を右に2つ動かすと右端の11の部分はなくなり、左端に00が増える)
pythonでは>>と書くことでシフト演算を行うことができる。
最初の例でいうと01010001を10進数表記に直すと
01010001=81
だから
81>>2
と書けば01010001を右に2つシフト演算できる。
print(81>>2)
これを実行すると「20」が出力される。
00010100＝20
だから確かにシフト演算された結果が出力されているのがわかる。
「アンド演算」
アンド演算は&と書く。2つの2進数それぞれの桁について、
1&1=1
1&0=0
0&1=0
0&0=0
と計算する演算。
たとえば
01010101
10110110
をアンド演算してみる。
縦に並んだそれぞれの桁について確認しよう。
右から0桁目：1&0=0
右から1桁目：0&1=0
右から2桁目：1&1=1
右から3桁目：0&0=0
右から4桁目：1&1=1
右から5桁目：0&1=0
右から6桁目：1&0=0
右から7桁目：0&1=0
ゆえに
01010101&10110110=00010100
となる。
pythonでは&と書くことでアンド演算を行うことができる。
01010101
10110110
をそれぞれ10進数表記に直すと
01010101=85
10110110=182
となるから
85＆182
と書けば01010101&10110110を計算できる。
print(85&182)
を実行すると「20」が出力される。
00010100＝20
だから確かにアンド演算された結果が出力されているのがわかる。
「シフト演算」と「アンド演算」を使えばどの桁が1となっているか？を確認できる。
具体的には以下の(1)～(3)を桁数回繰り返す。
(1)右にシフト
(2)1とアンド演算
(3)アンド演算の結果を確認
購入する参考書が以下の2進数で表される場合
01010001(=81)
「0冊目」
(1)01010001を右に0個シフト(つまり何もしない)
01010001>>0=01010001
(2)1とアンド演算
01010001&00000001=00000001=1
(3)アンド演算の結果を確認
1なので「0冊目」は買う
「1冊目」
(1)01010001を右に1個シフト
01010001>>1=00101000
(2)1とアンド演算
00101000&00000001=00000000=0
(3)アンド演算の結果を確認
0なので「1冊目」は買わない
「2冊目」
(1)01010001を右に2個シフト
01010001>>2=00010100
(2)1とアンド演算
00010100&00000001=00000000=0
(3)アンド演算の結果を確認
0なので「2冊目」は買わない
「3冊目」
(1)01010001を右に3個シフト
01010001>>3=00001010
(2)1とアンド演算
00001010&00000001=00000000=0
(3)アンド演算の結果を確認
0なので「3冊目」は買わない
「4冊目」
(1)01010001を右に3個シフト
01010001>>4=00000101
(2)1とアンド演算
00000101&00000001=00000001=1
(3)アンド演算の結果を確認
1なので「4冊目」は買う
「5冊目」
(1)01010001を右に5個シフト
01010001>>5=00000010
(2)1とアンド演算
00000010&00000001=00000000=0
(3)アンド演算の結果を確認
0なので「5冊目」は買わない
「6冊目」
(1)01010001を右に6個シフト
01010001>>6=00000001
(2)1とアンド演算
00000001&00000001=00000001=1
(3)アンド演算の結果を確認
1なので「6冊目」は買う。
「7冊目」
(1)01010001を右に7個シフト
01010001>>7=00000000
(2)1とアンド演算
00000000&00000001=00000000=0
(3)アンド演算の結果を確認
0なので「7冊目」は買わない
よって、「0冊目」、「4冊目」、「6冊目」を買うということがわかる。
このようにシフト→アンドを繰り返して各桁の情報を確認することができる。
【実装】
入力を受け取る。
CとAは一つのリストとして受け取った後、それぞれ別々のリストに格納する。
N,M,X=map(int, input().split())
C=[]
A=[]
for i in range(N):
CA=list(map(int, input().split()))
C.append(CA[0])
A.append(CA[1:])
答えを格納する変数としてansを作る。
最小コストを求めるので初期値はバカでかい数。
ans=10**20
ここからBit全探索。
探索範囲は(N桁全て0の2進数)~(N桁全て1の2進数)=0~(2^N-1)となる。
ゆえに
for i in range(2**N):
としてもよいのだがせっかくシフト演算を学んだのでそれで書いてみよう。
(N桁全て1の2進数)+1=1を左にN個シフト
と表せるから
for i in range(1<<N):
と書くことができる。
for i in range(1<<N):
例えばN=8のときはi=0,1,2,...,255(i=00000000,00000001,00000010,...,11111111)となり全てのパターンを網羅できる。
まず合計金額(=cost)、理解度(=skill)を初期化しよう。最初はそれぞれ0。
cost=0
skill=[0]*M
「0冊目」を買うか、「1冊目」を買うか、...を確認していく。
(1)右にシフト
(2)1とアンド演算
(3)アンド演算の結果を確認
買う場合は合計金額、理解度をプラスする。
for shift in range(N):
if i>>shift & 1==1:
cost+=C[shift]
for j in range(M):
skill[j]+=A[shift][j]
「(shift)冊目」は買うか？→右に(shift)個シフト&1=1か？を判定している。
探索が終わったら全ての理解度がX以上になっているか確認する。
skillの最小値がX以上となっているか確認すれば良い。X以上となっていてかつコストがそこまでに試した買い方より小さいなら答えを更新する。
if X<=min(skill):
ans=min(ans,cost)
最後に答えを出力する。ansが一度も更新されていなければ条件を満たす買い方は存在しなかったということ。
if ans==10**20:
print(-1)
else:
print(ans)
Bit全探索は考え方自体は難しくないが、自分で実装するとなると最初は戸惑うところだと思う。しかし書き方はワンパターンで一度覚えてしまえば次回以降は苦もなくスラスラと書ける。自分でこの問題を解けるまで時間をかけて頑張ろう。
【コード全文】
N,M,X=map(int, input().split())
C=[]
A=[]
for i in range(N):
CA=list(map(int, input().split()))
C.append(CA[0])
A.append(CA[1:])
ans=10**20
for i in range(1<<N):
cost=0
skill=[0]*M
for shift in range(N):
if i>>shift & 1==1:
cost+=C[shift]
for j in range(M):
skill[j]+=A[shift][j]
if X<=min(skill):
ans=min(ans,cost)
if ans==10**20:
print(-1)
else:
print(ans)
この記事は拙著「AtCoder 凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185