はじめに
初めまして。
普段AtCoderにPythonで参戦しているハチです。
今回は、bit全探索について初心者でも一から分かりやすく解説していきたいと思います。
実は僕自身、AtCoder歴は現時点で2ヶ月ほどで、まだまだ初心者です。ですが、初心者だからこそ分かる苦悩や引っ掛かりポイントがあると思います。
そこで、自分と同じようにAtCoder初心者でもこれを読めば「bit全探索」について理解できるような記事を書けたらと思います。
また、今回の記事と同じシリーズには以下のような記事もあるので、ぜひ興味があったら読んでみてください。
目次
- bit全探索とは
- 例題1
- 例題2
- その他コラム
- 練習問題
- AtCoderの典型問題(アルゴリズム)とは(超初心者に向けて。読まなくても大丈夫です)
- 超初心者に向けて(超初心者に向けて。読まなくても大丈夫です)
- おわりに
- 参考文献
bit全探索とは
では早速本題に入ります。
bit全探索とは何か？
bit全探索とは、とても大雑把に言うと、
「Yes」「No」の札を持ったN人の人が、それぞれ「Yes」「No」の札のどちらを上げるのか。
その全てのパターンについて「Yes」を「1」、「No」を「0」として調べ上げる方法と言えます。
例えば、3人がそれぞれ「Yes」「No」のどちらの札を上げるかの全パターンは以下のように書くことができます。
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
じゃあ、どうやってコードを書くの？と思った方、以下のようなコードで調べ上げることができます。
現時点で以下のコードを完璧に理解する必要はなく、「あーこんなもんね」くらいに見てやってください。
#bit全探索
#n人それぞれが「Yes」「No」どちらかについて。全パターン。
#「Yes」が「1」、「No」が「0」。
n=3
patterns=[]
for i in range(2**n):
p=[0]*n
for j in range(n):
#2進数表記した場合の下から数えて j 桁目（一番下の桁を 0 とします）が
#1 であるかどうかをチェックするためのコードは、(i >> j) & 1 となる。
if i >> j & 1:
p[j]=1
patterns.append(p)
print(patterns)
ただ、Pythonでは、itertools モジュールの product 関数を使うと簡単にbit全探索を実装できます。(Pythonありがとう！)
そのため、先ほどのコードはすっかり忘れてしまって大丈夫です。
これさえ使いこなせれば、この記事の内容、すなわちbit全探索についてはマスターしたといえるでしょう。
#bit全探索の基本コード(itertools モジュール)
from itertools import product
#n個について(長さn)
#n=3の場合 000,001,...のような
n=3
for pro in product((0, 1), repeat=n):
# proは長さN、各要素が整数 0 か 1 のタプル
print(pro)
ここまでで、bit全探索の基本についての説明は終了です。
正直まだ不安、分からない、といった方もいるでしょう。でも大丈夫っ！例題、練習問題を通して今まで説明した内容、基本コードを何度も使うことで次第に理解を深められると思います。
自信を持って次の例題に進みましょう。
例題では、今までの講義を自分の手を動かしながら理解する段階に入ります。
例題1
例えば、こんな問題を考えてみましょう。
N人に犬派、猫派どちらであるかを聞いた。
犬派なら1、猫派なら2のボタンを押してもらった。
西郷くんはどうやら大の犬好きらしい。そのため、
i(1<=i<=n)番目の人が犬派ならi点貰えるらしい。
合計M点になる場合は何通りあるか？
[入力例]
5 7 (N M)
[出力例]
3
解説
では、この問題はどのように解けば良いでしょうか？少し考えてみると、各々について「犬派」「猫派」という二つの選択肢が考えられるので、bit全探索使えそうですね。
では、早速この問題を解くためのコードを順を追って説明してみましょう。
ステップ1
以下のコードをVSCodeなどで実行してみてください。
from itertools import product
#n=3の場合
for pro in product((0, 1), repeat=3):
#合計M点の場合の数を更新。
print(pro)
すると、上のコードによって
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
のようにn=3の場合の全パターンが生成されます。
ステップ2
例えば上のコードで生成された全パターンのうちの「(1, 0, 1)」について考えてみましょう。
ここでは、pro=(1, 0, 1)となります。
よって、今回ではpro[0]=1であり、1番目の人は犬派となります。
「i番目の人が犬派ならi点貰えるらしい」とあるので、1点もらえます。
sum+=i+1として合計得点を更新します。
といったふうに、2人目、3人目についても同様に考えることができます。
それが以下のコードによって処理することができます。
sum = 0
for i in range(n):
#犬派なら合計点を更新する。
if pro[i] == 1:
sum+=i+1
ステップ3
以下のコードによって、先ほど計算した合計点がM点と一致した場合は1を返し、一致しない場合は0を返します。
#合計M点の場合は1を返す。
if sum==m:
return 1
else:
return 0
ステップ4
先ほど説明したように、main関数では、M点に一致した場合は1が返され、一致しない場合は0が返されます。
その結果をansに足すことで、合計M点になる場合は何通りあるかを計算することができます。
#求めたい値
ans = 0
for pro in product((0, 1), repeat=n):
#合計M点の場合の数を更新。
ans += main(pro)
print(ans)
全体コード
from itertools import product
def main(pro):
#合計点
sum = 0
for i in range(n):
#犬派なら合計点を更新する。
if pro[i] == 1:
sum+=i+1
#合計M点の場合は1を返す。
if sum==m:
return 1
else:
return 0
n,m = list(map(int,input().split()))
#求めたい値
ans = 0
for pro in product((0, 1), repeat=n):
#合計M点の場合の数を更新。
ans += main(pro)
print(ans)
例題2
もう一つ例題を解いてみましょう。
以下の記事で紹介されている問題は基本的で、とても勉強になります。ぜひやってみましょう！
その他コラム
bit & (1 << i)
練習問題
今回は、「bit全探索」について初心者でも分かりやすいように解説しました。
しかし、学校と同じように、どれだけ真面目に講義を受けてもテストでは満点を取れない、太刀打ちできない、と言ったことがあると思います。そこで、ここでは「bit全探索」の考えによって解くことのできる「bit全探索問題集」を紹介したいと思います。
ここで紹介した問題たちをマスターできれば、bit全探索なんて怖くない！bit全探索どんとこい！bit全探索楽しい！と思えるのではないでしょうか。
[bit全探索を練習できる問題集]
| 問題 | 配点 | Difficulty | 解答コード(Python) | コメント |
|---|---|---|---|---|
| ABC182 C - To 3 | 300点 | 292 | 解答 | 例題のコードを参考に |
| ABC190 C - Bowls and Dishes | 300点 | 472 | 解答 | 難易度が上がります。ただし、何が二択になっているのかを考えれば大丈夫！ |
| ABC167 C - Skillup | 300点 | 595 | 解答 | 2問目が理解できれば、3問目は自力でもできるでしょう |
| ABC173 C - H and V | 300点 | 653 | 解答 | 行、列それぞれについてパターンを考える必要があり、二重ループとなります。配列をコピーする部分で苦戦しました。 |
bit全探索についての内容はこれで以上です。
ここから先は超初心に向けての内容ですので、読まなくても全く問題ないです。
AtCoder初心者が、AtCoderのレーティングを上げるためにはこれから何をしたら良いのかについて書きました。
AtCoderの典型問題(アルゴリズム)とは
今回の記事でなぜ「bit全探索」を取り上げたのかについて説明したいと思います。
理由はズバリ、
AtCoderでレーティングを上げたい！C問題まで解けるようになりたい！と思っている方は、AtCoderで典型問題と言われているような以下のような解き方をマスターすることが重要だと思っているからです。
では、なぜそれが重要なのか？それは、以下に記した典型問題(アルゴリズム)が、大学受験における、「複素数平面」「2次曲線」「極限」「微分法」「積分法」のようなものだからです。
これらを使った解き方の基本をマスターすれば、それなりに点数が取れる、といったある種のボーダーラインとなります。
◎全探索
・二分探索(これから執筆予定)
・bit全探索
◎バケット・連想配列
◎区間分割・連長圧縮
◎グラフ
◎累積和
・数学的考察(幾つか考えるコツがある。偶奇についてなど)(これから執筆予定)
上の中で、◎がついた項目は、(通称)鹿本にかなり優しく丁寧に解説されている典型問題(アルゴリズム)です。これらの典型問題(アルゴリズム)は、ぜひ鹿本を買ってマスターしてください！(けんちょんさんという方が書かれた良書です。C++、Pythonでの実装例が書かれています。)
他にもたくさんありますが、初心者の方はひとまず初心者から脱却するために、上のような典型問題(アルゴリズム)をマスターすれば良いかと思います。ここまで出来れば、あなたも茶コーダーの仲間入りを無事果たすことができると思います。
超初心者に向けて(これから何をしたらよいか)
AtCoder初心者で、何をしたら良いのか分からない方には、以下の本をお薦めします。
こちらは、AtCoderの典型問題についてかなり優しく丁寧に解説されています。また、それぞれの典型問題(アルゴリズム)ごとに例題、練習問題が豊富に紹介されています。かなり鍛えられる良書です。
こちらは、私が初めて手に取ったAtCoder本です。後半の方はかなり難易度が高く、一つ目の本を解くことに注力しました。ただ、AtCoderで必要な入出力方法についてはこちらの本で学びました。
おわりに
ここまで読んで下さって本当にありがとうございました。
さて、どうでしたか。「bit全探索」をマスターすることはできましたか？
もしここが分からない、ここをこうしたらもっと分かりやすい記事になるんじゃない？と思った方、その他何でもコメントを下さると嬉しいです。より良い記事を書くための参考、モチベーションにしたいです。
これからは、冒頭でも示したAtCoderで典型問題と言われているような項目のうち、「二分探索」「数学的解法(幾つか考えるコツがある。偶奇についてなど)」について今回と同じような形で書いてみたいと思います。
ですので、今回分かりづらいと感じた箇所があればコメント等を参考に改善、修正をしながら執筆したいと思います。これからもよろしくお願いします。
今回の曲はこちら。米津玄師「KICK BACK」が楽しみです。
おすすめの曲があったらぜひコメント欄に書いてください！楽しみにしています。
参考文献
(スペシャルサンクス)
(その他)