競技プログラミング（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や拡散していただけると喜びます！
応用編：3つ以上の選択肢がある場合
bit全探索では、選択肢が $2$ つある場合を全探索しました。たまに、$3$ つ以上の選択肢がある問題もあります。このタイプの問題の解き方を解説します。
例題
ABC119 C - Synthetic Kadomatsu
解法
この問題は、それぞれの竹に対して
- 竹 $A$ を作るために使う
- 竹 $B$ を作るために使う
- 竹 $C$ を作るために使う
- 使わない
の $4$ つの選択肢があります。竹の使い方を決めたら、
- $3$ 本の竹に短縮魔法か伸長魔法を使って、長さを $A,B,C$ にする（コストは $|a - A| + |b - B| + |c - C|$）
- $使った竹の本数 - 3$ 回連結魔法を使う（コストは使った竹の本数を $t$ として、$10\times{t}-30$、元となる竹には連結魔法は不要なため）
ことで、この選び方でのコストを求めることができます。なお、無に伸長魔法を使って竹を作ることはできないので、$a,b,c$ のいずれかが $0$ になる選び方はできません。
さて、竹の使い方の組み合わせ数は（無効な選び方も含めて） $4^N$ 通りあるので、bit全探索の要領で全探索すれば、この問題を解くことができます。
productを使った実装
実際に、product関数を使って実装したコードがこちらです。
from itertools import product
INF = 1 << 60
def calc(pro):
H = [0] * 3
cnt = 0
for i in range(N):
p = pro[i]
if p != 3:
cnt += 1
H[p] += L[i]
cost = 10 * cnt - 30
for i in range(3):
if H[i] == 0:
return INF
cost += abs(A[i] - H[i])
return cost
N, *A = map(int, input().split()) # A, B, Cと3つの変数で受け取る代わりに、リストAのA[0], A[1], A[2]で受け取っています
L = [int(input()) for _ in range(N)]
ans = INF
# 0,1,2はそれぞれA,B,Cの竹に使う、3は使わない
for pro in product(range(4), repeat=N):
ans = min(ans, calc(pro))
print(ans)
product(range(4), repeat=N)で、(0, 1, 2, 3)のいずれかからなる長さ $N$ のタプルを全列挙しています。
選択肢が $2$ つの場合に比べて、かなり実装が面倒になってしまいます。整数を使う場合は、$4$ 進法の整数の各桁を取り出せばいいのですが、ビット演算を使えず非常に面倒になります。
再帰関数で書いたほうが楽
このタイプの問題は、再帰関数を使って解くことをおすすめします。
INF = 1 << 60
def rec(i, a, b, c):
if i == N:
if a == 0 or b == 0 or c == 0:
return INF
return abs(A - a) + abs(B - b) + abs(C - c) - 30
# 竹を使う場合、コスト+10している
return min(rec(i + 1, a + L[i], b, c) + 10,
rec(i + 1, a, b + L[i], c) + 10,
rec(i + 1, a, b, c + L[i]) + 10,
rec(i + 1, a, b, c))
N, A, B, C = map(int, input().split())
L = [int(input()) for _ in range(N)]
ans = rec(0, 0, 0, 0)
print(ans)
rec(i, a, b, c)は、次に選択する竹がL[i]であり、長さ $a, b, c$ の竹を持っている状態です。
$4$ 通りの遷移は、iを $+1$ して
- 竹 $a, b, c$ それぞれに竹 $i$ を連結して $L_i$ 伸ばし、コスト $10$ を払う（
+10と書いている部分がそれです） - 竹 $i$ を使わないでコスト $0$
に対応します。求めるものは最小値なので、$4$ パターンをmin関数に入れ、最小値を返しています。
$i=N$ になったら、竹の伸長、短縮コストを求め、竹 $3$ 本は連結魔法を使わないので $-30$ をして返します。
普通のbit全探索も再帰で書ける
$4$ パターンの選び方がある問題を再帰関数で書きましたが、$2$ パターンの選び方がある通常のbit全探索の問題も再帰関数で解くことができます。個人的には普通にbit全探索を書いたほうが楽だと思いますが、再帰関数に慣れている人はもしかするとこちらのほうが書きやすいかもしれません。
記事リンク（再掲）
1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題を解きます。