はじめに
みなさんbit全探索はご存じでしょうか？
bit全探索は2進数で状態を表していますが、
「別に2進数じゃなくても行けるのでは？」
と思ったのが、この記事を書くきっかけです。
bit全探索を拡張して、k進数でbit全探索を出来るようにしてみたいと思います。
本編
bit全探索について
bit全探索は、競技プログラミングでは典型の全探索アルゴリズムです。
例えばこんな問題があったとします。
bit全探索を使用する例題
8個の商品があります。
それぞれの値段は以下の通りで、在庫はそれぞれひとつずつです。
1, 3, 4, 5, 6, 8, 10, 14
それぞれの商品について買うか買わないかを選ぶ時、支払う金額の種類は何種類ありますか？
この問題を見た時に、「各商品について選ぶか選ばないかを決め、選ぶと決めた商品の合計を出し、その合計の種類数を数えると解けそう」と思います。
こんな時に使えるのがbit全探索です。
各商品についての"選ぶ"か"選ばない"の2択を、数字を2進数で表した各桁の$0,1$に対応させて全探索をします。
例
例えば商品1,3,4,6を選ぶ時を考えます。
各商品を選ぶことを1、選ばないことを0と表現してこの状況を2進数で表すとこうなります
00101101
2進数の数字の各桁が右から商品1,2,...,8の状態を表しています。
今回は1,3,4,6桁目が1になっており、この場合の商品の金額の合計は18になります。
他の状態も考えると、00000000 ~ 11111111(2進数)の数字で全ての選ぶ選ばないを表現することができ、これがbit全探索です。
実際のコード
コードに書くとこんな感じでしょうか。言語はPythonです。
N = int(input())
price = list(map(int, input().split()))
price_set = set()
for bi in range(1<<N):
price_sum = 0
for i in range(N):
if bi>>i&1: price_sum += price[i]
price_set.add(price_sum)
print(len(price_set))
計算量は$O(2^NN)$なので、問題にもよりますが$N\leq18$くらいなら現実的な制約になりそうです。
状態数は別に2つじゃなくても良いのでは？
これがbit全探索ですが、ここで思った方がいるかもしれません。
bit全探索は"選ぶ"、"選ばない"で状態が2つだったので2進数の各桁で状態を表したのでした。
じゃあ、3進数なら状態を3つ表現できるのでは？
矢木に電流走る
bit全探索は数字を2進数で表して各桁$0,1$で状態を表現しています。
じゃあ、3進数なら各桁は$0,1,2$になって状態を3つ表現できるのでは？
さらに拡張して、k進数なら各桁は$0,1,...,k-1$になってk個状態を表現できるのでは？
そうは思いませんでしょうか。
k進数に拡張したら解ける例題
bit全探索をk進数に拡張してこんな問題を解いてみます
k進数bit全探索で解ける例題
8個の商品があります。
それぞれの値段は以下の通りで、在庫はそれぞれひとつずつです。
1, 3, 4, 5, 6, 8, 10, 14
AさんとBさんはそれぞれの商品について買うか買わないかを選びます。
一方が選んだ商品はもう一方は選ぶことが出来ない時、それぞれが支払う金額の差の金額の種類は何種類ありますか？
前の問題では状態が"選ぶ"、"選ばない"の2種類でしたが、今回は各商品の状態を"Aが選ぶ"、"Bが選ぶ"、"選ばない"の3種類にすると解けそうです。bit全探索を3進数に拡張して解いてみます。
例
例えば、Aが商品1,4、Bが商品2,7,8を選ぶ時を考えてみます。
各桁の数字を0: 選ばない, 1: Aが選ぶ, 2: Bが選ぶと対応させると状態を表す数字は3進数でこうなります。
22001021
他の状態も考えると00000000 ~ 22222222(3進数)の数字で全状態を表現できそうです。
実際のコード
コードに書くとこんな感じです。
N = int(input())
price = list(map(int, input().split()))
price_set = set()
for bi in range(3**N):
sum_A, sum_B = 0, 0
for i in range(N):
if bi//(3**i)%3 == 1: sum_A += price[i]
elif bi//(3**i)%3 == 2: sum_B += price[i]
price_set.add(abs(sum_A-sum_B))
print(len(price_set))
計算量は$O(3^NN)$です。$N\leq12$くらいなら現実的でしょうか。
4進数bit全探索で解けた問題
AtCoderの過去問を解いていてk進数bit全探索で解けた問題があったので紹介します。
順列と仕切りを使用した解法
最初に提出した解法はこちらです。
竹の並び順を全探索し、その並び順に挟む3つの仕切りを全探索する解法で解きました。
計算量は$O(N\times N!\times _{N-1}C_3) \fallingdotseq 1.1\times 10^7$です。
これでも十分間に合いました(0.800ms)
k進数bit全探索を使用した解法
解説を読んだ後に4進数bit全探索でも提出してみました。
4進数の各桁を0: Aが選ぶ, 1: Bが選ぶ, 2: Cが選ぶ, 3: 選ばないとして全探索しています。
計算量は$O(4^N\times N) \fallingdotseq 5.2\times 10^5$となって、大幅に計算量が改善(0.228ms)しました。
おわりに
bit全探索は無駄なく全探索が出来る
bit全探索の良い所は、状態を表す数字に1増やすだけで次の状態に遷移出来る所です。
また、最初の方法では同じ状態を重複して数えてしまっていましたが、bit全探索なら各状態を重複なく数えることが出来ます。
k進数bit全探索を手段として持っておくと、状態が2つではない場合においてもbit全探索の良さを生かした全探索が出来るのではないかと考えます。
ぜひ、試してみてください。