こんにちは。
Atcoderを初めて1.5ヶ月緑コーダーのうなぎです。
今回は@e869120 さんの作成されたレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】のbit探索に関する問題を初心者が実際にどう考えて解いていたのかをこの記事に記して置こうと思います。
あくまで、初心者が初心者の時に感じたことを書いている記事となっています。
bit全探索
bit全探索を用いる例としてはn個数の選択肢が与えられた時にそれぞれについて「選択する」or「選択しない」（「買う」or「買わない」とか）のパターンを全て試したい時に使う。（つまり$2^n$通り）
要は
sample.py
for i in range(2):
for j in range(2):
for k in range(2):
for l in range(2):
....
みたいに書くとやってられないため、この「選択する」or「選択しない」を2進数の0と1に見立てて全探索するということ。全探索のためnはだいたい30よりは小さいイメージ。逆にnが30未満くらいの範囲ならbit全探索が求められていることを疑っても良い？？
基本的な書き方
sample.py
for i in range(1<<n): #全パターン列挙
for j in range(n): #各bitについて
if (i>>j)&1: #選んだパターンiのうちどのbitが立っているか
....
のようになります。
初心者に分かりにくい点
先輩方のコードを参考にした時、すっと入ってこなかった部分をまとめました。
-
(1<<n)と2^nは同じ。<<はbit演算子で1をn個左にシフトするという意味。例として1<<4は2進数で0b10000で10進数で16となり2^4と一致する。 -
(i>>j)&1は選んだiのj+1桁目と1のANDを取るというもの。つまりiのj+1桁目が1かどうかを判定する。ここでjは0からn-1までなので、iを2進数で100とした時、100と1、10と1、1と1、...とbit演算子でずらしていったものと1を比較することになる。
もう一つはi&(1<<j)も見る。本質的には同じ。iと1をjだけずらして各桁が1かどうかを見る。
ちなみに自分は最初の頃この書き方を知らず、あるパターンiをbin(i)[2:]というめちゃくちゃ面倒なことをしていた。（これはbin(i)で'0b100'が取り出せて0bを除く。その後、各値が'1'かどうかを判定する。）
以下です笑
sample.py
# 最初の頃のクソコード
for i in range(2**N):
I = bin(i)[2:]
I = I.zfill(N)
for j in range(len(I)):
if I[j]=='1':
....
- 「立っている」という用語はそれが
1であるかどうか。
解いた問題
@e869120 さんの作成されたレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の該当問題(64-67)を2020年8月時点でレート900の私が解いた感想です（あくまで感想です、いかに述べる解き方などが最適解とは限りません）。
一緒に精進する人にとってのモチベーションになれば幸いです。
以下該当問題を解いた感想（ネタバレ注意）
-
ALDS_5_A - 総当たり
基本問題。nが20以下なので全探索しても$10^6$程度だからゴリ押せるという発想。あとは基本的なbit探索。 -
AtCoder Beginner Contest 128 C - Switches
nが10以下なので高々1024通りについて考えれば良い。色々勉強するとこういう問題でシンプルに全探索すればいいのだと気づかなくなりやすい気がする。各場合についてスイッチがonのものを数えるだけ。 -
AtCoder Beginner Contest 002 D - 派閥
これもnが12以下のケース。各桁1のものだけ集めてそれらが全て友達であるかを$\rm O(n^2)$でみていく。 -
JOI 2008 予選 5 - おせんべい
rが10以下であることに注目して、全ての行の表裏で全探索する。あとは各列で表と裏の大きい方をカウントすれば良い。（裏が多かったらその列はひっくり返すと考える。）pypy使えば2s以内に抑えられる。 -
Square869120Contest #4 B - Buildings are Colorful!
単調増加が続く部分は確実に見えるのでその部分を取り除いた箇所でbit探索すれば良い。
最後に
今回はbit探索についてまとめてみました。
ここが分かりにくかったとか、もっとこう書いた方が良いなどのアドバイスがあれば遠慮なく質問してください。