競技プログラミング（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や拡散していただけると喜びます！
実践編 : AtCoderの問題を解いてみよう
bit全探索に慣れるために、AtCoderのbit全探索を使う問題 $6$ 題 を実際に解いてみましょう。
解答コードは以下の $3$ パターンを用意しました。
- Python（productを使った実装）
- Python（ $2$ 進法を使った実装）
- C++（ $2$ 進法を使った実装）
できるだけ自力で解いて、bit全探索の実装に慣れることをおすすめします。もし詰まった場合は、簡単なヒントを載せてあるので、まずはそちらを見てください。
第1問
基本的な問題ですが、少し問題文がややこしいので注意してください。
ヒント
ヒント
bit全探索するのは、人がどちらの皿にボールを置くかです。
どの皿にボールが何個載せられているか、カウントしましょう。（ボールの数は1個以上なら何個でも変わらないので、TrueかFalseで管理してもいいです）
判定部分は、問題文通りにforループで判定すれば良いです。
コード
Python（product）: コード
Python（$2$ 進法）: コード
C++: コード
おまけコード
Pythonではproduct()関数に $i$ 人目が選ぶ皿の選択肢のタプルそのものを渡すことで、皿の選び方そのものを直接全列挙できるので、楽をできます。
Python（productおまけ): コード
第2問
やや実装は重いですが、基本的な問題です。
ヒント
ヒント
答えの初期値はINF（適当な巨大な整数）にしておきます。
判定部分は関数に分けたほうがコードがぐちゃぐちゃにならずに済みます。
判定関数では買った参考書の合計金額と、各アルゴリズムの理解度を管理します。
最後に、理解度の条件を満たしているなら合計金額を、満たしていないならINFを返します。
全パターン試して答えがINFならば、どうやっても達成不可能なので-1を出力すればいいです。
ACコード
Python（product）: コード
Python（$2$ 進法）: コード
C++ : コード
第3問
bit全探索以外の解法もあります。bit全探索は若干実装が重くなる代わりに、何も考えなくて良いので楽かもしれません。
ヒント
ヒント
Nを文字列で受け取ったほうが楽です。
使う桁、使わない桁をbit全探索して、使う桁を空の文字列に追加し、最後に文字列を整数に変換し、3の倍数か判定しましょう。
すべての桁を消してしまう場合の処理に気をつけてください。
ACコード
Python（product）: コード
Python（$2$ 進法）: コード
C++ : コード
第4問
問題文をよく読んで判定部分を書けば、それほど難しい問題ではないはずです。
ヒント
ヒント
電球iはスイッチxと繋がっている、という入力が与えられますが、スイッチxが電球iとつながっている、の形で持つほうが実装が楽です。
ACコード
Python（product）: コード
Python（$2$ 進法）: コード
C++ : コード
第5問
行と列の $2$ 通りの操作がありますが、これもbit全探索で解けます。
ヒント
ヒント
行と列、それぞれどれ塗るか管理するタプルや整数を、二重ループで別々に作ったほうがわかりやすいです。（計算量は変わりません）
ACコード
Python（product）: コード
Python（$2$ 進法）: コード
C++ : コード
第6問
やや難易度の高い問題ですが、ORやXORに惑わされなければ解けるはずです。
ヒント
ヒント
ORの演算子は|で、XORの演算子は^ です。ORやXORが何をやっているか知らなくても解けます。
N-1箇所、|か^を入れる場所があると考えるとよいです。
ACコード
Python（product）: コード
Python（$2$ 進法）: コード
C++ : コード
記事リンク（再掲）
1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題を解きます。