はじめに
今回から、備忘録としてアルゴリズムの解説をしていきます。
「わかりやすく短く」を意識して執筆していきます。
コードは毎回Pythonで実装していきます。
第１回である今回のテーマは、C問題頻出の bit全探索 ですます。
この記事を理解するために必要な前提知識
誰でも理解できるという題ですが、前提知識がなければどうにもなりません
下記の知識は理解している前提で執筆いたします
記事リンク
誰でも理解できるシリーズのリンク一覧です。ぜひご覧ください。
- 【bit全探索】誰でも理解できるアルゴリズム解説（今回の記事）
- 【座標圧縮】誰でも理解できるアルゴリズム解説
bit全探索とは？
簡単にいうと、選ぶか選ばないかを全パターン探索する方法です。
例えば、5個のみかん
それぞれに対して、『選ぶ』『選ばない』、『食べる』『食べない』 といった二択を当てはめていく感じです。実際に当てはめると以下のようになります。
|
１ |
2 |
3 |
4 |
5 |
|
|---|---|---|---|---|---|
| 1 | 選ばない | 選ばない | 選ばない | 選ばない | 選ばない |
| 2 | 選ばない | 選ばない | 選ばない | 選ばない | 選ぶ |
| 3 | 選ばない | 選ばない | 選ばない | 選ぶ | 選ばない |
| 4 | 選ばない | 選ばない | 選ばない | 選ぶ | 選ぶ |
| 5 | 選ばない | 選ばない | 選ぶ | 選ばない | 選ばない |
| … | |||||
| 31 | 選ぶ | 選ぶ | 選ぶ | 選ぶ | 選ばない |
| 32 | 選ぶ | 選ぶ | 選ぶ | 選ぶ | 選ぶ |
5個だと32通り、つまり2^5通り(2×2×2×2×2)になります。
以下のように『選ぶ』『選ばない』を二進数にするとイメージが湧きやすいと思います。0は『選ばない』、1は『選ぶ』です。
|
１ |
2 |
3 |
4 |
5 |
|
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 1 |
| 3 | 0 | 0 | 0 | 1 | 0 |
| 4 | 0 | 0 | 0 | 1 | 1 |
| 5 | 0 | 0 | 1 | 0 | 0 |
| … | |||||
| 31 | 1 | 1 | 1 | 1 | 0 |
| 32 | 1 | 1 | 1 | 1 | 1 |
普通の全探索じゃダメなの？
結論、ダメな場合があります。
以下の問題で考えてみましょう。
問題1
「みかんが 20個 あります。それぞれのみかんには Xi個の粒 が入っています。 2個 のみかんを食べた時、粒の数が 10の倍数 になるパターンは何通りあるか出力せよ。」
これは２重ループで解けますね。iとjを使って、2つのみかんを食べる全パターンを探索することができます。
よって、これは普通の全探索OKです
問題2
「みかんが 20個 あります。それぞれのみかんには Xi個の粒 が入っています。 N個 のみかんを食べた時、粒の数が 10の倍数 になるパターンは何通りあるか出力せよ。」
先ほどの問題と違うのは、何個のみかんを食べるかがNで表されているところです。
普通の全探索の場合、もしNが2なら二重ループ、Nが3なら三重ループで解くことになります。2,3くらいならいいですが、もしNが15なら15重ループにもなってしまいます
再帰を使えば無理ではないですが実装が難しくなってしまいます。
よって、これは普通の全探索NGです
ここでbit全探索が使えます！
先ほどの例では「5個のみかんで2^5通り(32通り)」のパターンがありましたよね？今回のみかんの数は20個なので、全探索したら「2^20通り(約100万通り)」。AtCoderでは処理が20億を超えるとTLEするといわれているので、100万なら余裕でACできます。
bit全探索のコードを見てみよう
みかんの例の問題を実装した解答です。
# 入力
N = int(input()) # 食べるみかんの数
X = list(map(int, input().split())) # みかんの粒の数List
ans = 0
# bit全探索----------------------------------------------
for bit_num in range(1<<20): # 2^20回(みかんの数)繰り返す
eat_grain = 0 # 食べた粒の合計数
eat_orange = 0 # 食べたみかんの数
for i in range(20): # 20回(みかんの数)繰り返す
# 2進数にしたときのi桁目が1なら食べる
if bit_num & (1 << i):
eat_grain += X[i]
eat_orange += 1
# 食べたみかんの数がN個でなければスキップ
if eat_orange != N:
continue
# 食べた粒の数が10の倍数ならansに代入する
if eat_grain % 10 == 0:
ans += 1
# ------------------------------------------------------
# 出力
print(ans)
bit演算特有の記述について説明します。
・1<<20
これは2^20を表します。
'<<'はシフト演算です。0b1(0bは二進数を表す)を左に20回シフトすると、0b100000000000000000000、これを10進数になおすと1,048,576(2^20) になります。つまり「1<<20 は 2^20 になる」というわけです。
・bit_num & (1 << i)
これはbit_numのi+1桁目が1かどうかを判定します。
'&'はアンド演算です。iが3の場合「1<<i == 0b1000」になります。よって、bit_numの右から4桁目が1なら1(True)、0なら0(False)という判定になるわけです。
今回のオーダは、2^20通りそれぞれに対して20個のみかんのどれを食べたのかを調べるため、O(20×2^20) になります。
bit全探索の注意点
bit全探索は先ほどの通り、2^N通りの全探索です。
Nが30を超えるあたりで、AtCoderでTLEになってしまう20億を超えてしまいます。
(実際は、他の処理でもループが発生するので、Nが20を超えたあたりからは事前に計算量を考えましょう。)
TLEしそうな時は以下を検討します。
- 他のアルゴリズムを利用する
(動的計画法(DP)や累積和など) - ソートや重複排除など、データを工夫して減らしてからbit全探索する
(数字の種類だけでいいなら0~9で10種類、2^10通りでいける等)
AtCoderの問題例
実際の問題をまとめてくださっている記事がありましたので載せておきます。
【AtCoder】ビット全探索〜問題まとめましたっ！〜
おわりに
今回はbit全探索を解説していきました。
こうしたらもっとわかりやすくなるなど、ご教示いただけると嬉しいです。
今回はとってもいい記事になったね。明日はもっといい記事になるよね。ハム◯◯🐹
Let's AtCoder!!!
参考
- 最速で緑になる-基礎・典型50問詳細解説-佐野
https://amzn.asia/d/hCwPX57 - こわくないbit全探索1 入門編: bit全探索ってなに？【競プロ解説】
https://qiita.com/u2dayo/items/68e35815659b1041c3c2 - 【AtCoder】ビット全探索〜問題まとめましたっ！〜
https://qiita.com/Jessica_nao_/items/83bcc7b43aadccb51ac1