競技プログラミング(AtCoder)初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。
この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。
記事リンク
1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。
質問先など
ご指摘・ご質問はツイッター・マシュマロ・Discordサーバーまでお気軽にどうぞ!
Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます!
bit全探索ってなに?
bit全探索とはどんなアルゴリズムなのでしょうか。bit全探索は、名前の通り『全探索』をするアルゴリズムです。『全探索』はB問題でも出題されるので、みなさんもやったことがあると思います。
簡単な全探索の例
全探索がなにかおさらいするために、AtCoderのB問題を紹介します。
$a+b+c≤S$ かつ $a \times b \times c \leq T$ を満たす非負整数の組$ (a,b,c)$ はいくつありますか?
制約
- $0 \leq S \leq 100$
- $0 \leq T \leq 10000$
- $S, T$ は整数である。
(非負整数とは、$0$ 以上の整数のことです)
この問題は $a,b,c$ としてありえる組み合わせをすべて試してみて、$a+b+c\le{S}$ かつ $a\times{b}\times{c}\le{T}$ を満たす組み合わせの数を数えればいいです。$a+b+c\le{S}$ なので、$a,b,c$ のうち $2$ つを $0$ にすると残り $1$ つはどんなに大きくても $S$ ですから、それぞれ $0$ ~ $S$ を三重ループですべて調べて、$2$ つの条件を満たす非負整数の組の数を数えればいいです。
S, T = map(int, input().split())
ans = 0
for a in range(S + 1):
for b in range(S + 1):
for c in range(S + 1):
if a + b + c <= S and a * b * c <= T:
ans += 1
print(ans)
これが全探索です。
bit全探索もただの全探索
『bit全探索』もこの問題と同じように、ありえる組み合わせをすべて試す全探索の一種です。「ありえる組み合わせすべて」を列挙できれば、あとはただの全探索と違いはありません。
『bit全探索』という名前が難しそうで、イメージがつきづらいのがとっつきづらい原因だと思っています。実際にやっていることは『使う・使わないを全探索』『選ぶ・選ばないを全探索』程度のことです。これなら簡単そうに見えませんか。
bit全探索は何ができるの?
『bit全探索』は、どのような問題に使えて、どういうことをするアルゴリズムなのかを説明します。
使える問題
- 複数ある商品(最大 $20$ 個程度)それぞれについて『買う』『買わない』とか、複数ある整数をそれぞれについて『選ぶ』『選ばない』といった、$2$ 種類の選択肢が複数ある問題
後で問題の具体例をいくつか載せるので、そちらを見ていただけると理解しやすいと思います。
bit全探索でやること
- そのタイプの問題で、『ありえる選択肢の組み合わせ方を全てもれなく列挙』して、『一つ一つの組み合わせに対して計算や判定を行う』ことで、答えを見つけるアルゴリズム
『一つ一つの組み合わせに対して計算や判定を行う』部分は、B問題の全探索問題でやることと変わりません。bit全探索を覚えようとしているみなさんが苦労することはないはずです。(たまに実装が重い場合もありますが……)
『ありえる選択肢の組み合わせ』ってどんな感じ?
簡単な例で、『ありえる選択肢の組み合わせ』すべてを見てみましょう。
$3$ 個の商品 $1,2,3$ があって、それぞれ $1$ 個だけ『買う』か『買わない』か選択できる。
$3$ 種類の商品を『買う』か『買わない』かの組み合わせパターンは、全部で以下の $8$ 通りです。(何も買わない場合も含む)
商品1 | 商品2 | 商品3 | |
---|---|---|---|
1 | 買う | 買う | 買う |
2 | 買わない | 買う | 買う |
3 | 買う | 買わない | 買う |
4 | 買わない | 買わない | 買う |
5 | 買う | 買う | 買わない |
6 | 買わない | 買う | 買わない |
7 | 買う | 買わない | 買わない |
8 | 買わない | 買わない | 買わない |
上の表のように、選択肢の組み合わせを全て列挙して、各パターンについて計算や判定をすることで、答えを探します。
解ける問題の具体例
では、『$2$ 種類の選択肢が複数ある問題』の『ありえる選択肢の組み合わせ』すべてを全探索することで解ける問題の具体例を $3$ つ紹介します。雰囲気を掴むだけで構いませんから、あまり真面目に考えずに軽く読み流す程度で構いません。
限られた所持金で複数の商品から買うものを選び、満足度を最大化する問題
$N$ 個の商品があります。$i$ 番目の商品の値段は $A_i$ 円で、買ったときに得られる満足度は $B_i$ です。
あなたはそれぞれの商品を『買う』か『買わないか』、自由に決めることができます。(一つの商品を $2$ 個以上買うことはできません)あなたは $W$ 円持っていて、はじめの満足度は $0$ です。合計金額が $W$ 円以下になるように商品を買って、得られる満足度の最大値を求めてください。
$N$ 個の商品について『買う』か『買わないか』の選択肢が存在します。先ほどの表のようにもれなく『買う』『買わない」の組み合わせ全パターンを調べて、合計金額が $W$ 円以下になる組み合わせの中で、 満足度が最大のものが答えです。
スイッチを押すか押さないか
$N$ 個のスイッチ $1$ ~ $N$ と $M$ 個の電球 $1$ ~ $M$ があります。はじめ、電球は全て消灯状態です。
あなたは、$N$ 個のスイッチそれぞれに対して、『 $1$ 度だけ押す』か『押さない』のどちらかの行動ができます。
$i$ 番目のスイッチを押すと、$C_i$ 個の電球 $A_{i1},A_{i2},\dots,A_{iC_i}$ の電球の消灯/点灯状態が切り替わります。つまり、$A_{ij}$ の電球が消灯状態ならば点灯状態に、点灯状態ならば消灯状態になります。
うまくスイッチを押すことで、すべての電球を点灯状態にできるか判定してください。
「スイッチ $1$ を押すと、$3$ 個の電球 $1,2,4$ の状態が切り替わる」という雰囲気の問題です。
前提として、この問題はスイッチを押す順番は関係なく、どのスイッチを押すかだけで、最終的な電球の状態は決まります。(切り替わった回数が奇数回なら点灯、偶数回なら消灯で、最終的に切り替わった回数に押す順番は関係ないからです)
順番はどうでもいいので、どのスイッチを押すかだけを考えればいいです。
スイッチを『押す』『押さない』の組み合わせを全パターン列挙して、各パターンにそれぞれについて、電球の状態がどうなるかシミュレートします。こうして、全ての電球が点灯するスイッチの押し方が存在するか調べればいいです。
+を入れるか×を入れるか
$N$ 個の正の整数 $A_1,A_2,\dots,A_N$ が空白区切りで与えられます。
隣り合う数字の間の空白は $N-1$ 箇所あります。($A_1$ と $A_2$ の間、$A_2$ と $A_3$ の間、$\dots$ 、$A_{N-1}$ と $A_N$ の間)あなたは $N-1$ 箇所の空白それぞれに
+
または×
どちらかの符号を自由に書き込んで、$1$ つの数式を完成させます。計算の結果が $X$ ちょうどになる、符号の書き込み方が存在するかを判定してください。存在するならば、その書き込み方を出力してください。複数の書き込み方がある場合、そのうちどれを出力しても正解になります。
『$3\ \ 3\ \ 2$ の $2$ 箇所の空白に+
か×
を入れて、計算結果を $11$ にできますか?』という雰囲気の問題です。今の例だと、$3\times{3}+2=11$ が正解になります。
$N-1$ 箇所の空白それぞれに対して、+
か ×
のどちらかを書き込む $2$ 通りの選択肢があります。これも書き込み方を全パターン試してみて、計算結果が $X$ になるものがあるか探せばいいです。
bit全探索は、Nが小さいときにしか使えない
ここで、注意すべきことがあります。bit全探索は、選択肢の数 $N$ が比較的小さいときでないと使えません。(目安はすぐ下で書きます)
組み合わせ数は $N$ に対して指数関数的に増えていくので、ある程度大きい $N$ では組み合わせ数が大きくなりすぎて、全探索することが不可能になるからです。
組み合わせ数は2^N通り(指数関数的に増えていく!)
『選ぶ』『選ばない』を選択する対象の数と、総組み合わせ数の関係を探ってみましょう。
『選ぶ』『選ばない』の対象が $1$ 個なら、組み合わせは $2$ パターンです。
対象が $2$ 個になると、組み合わせは $2\times{2}=4$ パターンです。
対象が $3$ 個になると、組み合わせは $2\times{2}\times{2}=8$ パターンです。
このように、『選ぶ』『選ばない』の対象が $1$ 個増えると、組み合わせ数は $2$ 倍になります。一般化すると、『選ぶ』『選ばない』の対象が $N$ 個 あるとき、組み合わせ数は $2^N$ 通りです。
$2^N$ というのは、指数関数です。「指数関数的な増え方」という言い方をするように、$N$ に対して急激に組み合わせ数は増えていきます。
Nと組み合わせ数の具体例
次の表は、$N$ と $2^N$ (組み合わせの総数)の関係の表です。
$N$ | $2^N$ | コメント |
---|---|---|
$10$ | $1024$ | 頑張れば人力でも全パターン試せる程度です。(やりたくはない) |
$16$ | $65536$ | 人力では人海戦術でないと厳しいですが、現代のコンピュータを使えば一瞬です。 |
$20$ | $1048576$ | 計算量が $O(N2^N)$ になるパターンのbit全探索が想定解の問題では、$20$ 程度の制約が上限になってることが多いです。 $2^N$ 通りの組み合わせの $1$ 通りにつき $O(N)$ で計算や判定を行うと、全体では $O(N2^N)$ の計算量になります。 |
$30$ | 約 $10$ 億 | 現代のコンピュータをもってしても、計算に $10$ 秒以上かかります。競技プログラミングの制限時間は $2$ 秒のことが多いので、bit全探索は解法として使えません。 |
$40$ | 約 $10^{12}$ | 一般的なコンピュータ $1$ 台では、計算に数十分かかります。 まだ覚える必要はありませんが、この程度の制約では、半分全列挙というbit全探索の応用テクニックを使うと高速に解ける場合があります。 |
$100$ | 約 $10^{30}$ | たったの $N=100$ ですら、宇宙が終わるまで計算し続けても、全く終わらないほど莫大な組み合わせ数になります。 |
この表を見るとわかるように、$N$ が少し大きくなるだけでも、爆発的に組み合わせ数が増えてしまいます。
処理の複雑さにもよりますが、$N\le{20}$ が実行時間制限に余裕を持ってbit全探索を使える目安です 。もう少し大きい $N$ でもbit全探索が想定解の可能性はあるので、あくまで目安程度にしてくだい。
記事リンク(再掲)
1. 入門編 bit全探索ってなに? : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう! : 簡単な例題(部分和問題)で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう! : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう! : AtCoderのbit全探索を使う問題のヒントとコード(Python・C++)を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう! : 再帰関数を使ってbit全探索に似た問題を解きます。