アルゴリズム初心者がbit全探索をまとめてみた

bit全探索とは？

bit全探索とは、各要素を「選ぶ」「選ばない」の2択として扱い、すべてのパターンを探索する方法です。「0」と「1」の二進数を使って表現されます。「0」は選ばない（否定）、「1」は選ぶ（肯定）というイメージです。

例えば、5枚のカードがあり、それぞれを「引く」「引かない」の全パターンを考えると、以下のようになります。

	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
			…
29	1	1	0	0	0
30	1	1	1	0	1
31	1	1	1	1	0
32	1	1	1	1	1

1. 全通りについて

5枚のカードがある場合、その選択肢は2通り（選ぶor選ばない）です。
したがって、2の5乗である2^5 = 32通りの組み合わせが存在します。

2. 二進数との関係

各カードの選択状態を二進数で表現すると、次のようになります。

• 1枚目のカードだけを引かない場合
  → 「11110」（2枚目から5枚目までは引くが、1枚目だけ引かない）

• 3枚目と5枚目だけを引く場合
  → 「00101」（3枚目と5枚目を引き、他のカードは引かない）

このように、bit全探索では「二進数」で選択状態を管理し、全パターンを網羅することができます。

bit全探索の使用例

次に、bit全探索がどのような場面で使われるかを具体例を通じて説明します。

例1：2枚のカードの合計が10の倍数になる組み合わせを探す

カードが5枚あり、それぞれに数字が書いてあるとします。
2枚のカードを引き、その合計が10の倍数になる組み合わせが何通りあるかを求めます。
これは通常の全探索（2重ループ）で解けます。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        // カードの枚数
        int N = 5;
        int[] cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = scan.nextInt();
        }

        int ans = 0;
        
        // 2枚のカードの組み合わせを全探索
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                int sum = cards[i] + cards[j];
                
                // 10の倍数ならカウント
                if (sum % 10 == 0) {
                    ans++;
                }
            }
        }

        System.out.print(ans);
    }
}

例2：N枚のカードの合計が10の倍数になる組み合わせを探す

今度は、N枚のカードを引いて、その合計が10の倍数になる組み合わせを求めます。
多重ループでは処理時間がかかりすぎるため、ここでbit全探索が有効になります。

import java.util.Scanner;

public class CardCombinationBitSearch {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] cards = new int[5];
        for (int i = 0; i < 5; i++) {
            cards[i] = scanner.nextInt();
        }

        int N = scanner.nextInt();
        int ans = 0;

        // bit全探索
        for (int bit = 0; bit < (1 << 5); bit++) {
            int sum = 0;
            int selectedCount = 0;

            for (int i = 0; i < 5; i++) {
                if ((bit & (1 << i)) != 0) {
                    sum += cards[i];
                    selectedCount++;
                }
            }

            if (selectedCount == N && sum % 10 == 0) {
                ans++;
            }
        }

        System.out.println(ans);
    }
}

解説

• bit < (1 << 5)
  1を5回左にシフト（1 << 5）することで、2^5（32）通りの組み合わせが生成されます。
  0から32まですべてのビット列（5ビット）を網羅するためのループです。

• bit & (1 << i)
  この式は、bitのi番目の桁が1かどうかを確認するためのビット演算です。具体的には、1 << i で「i番目が1の二進数」を作り、それと bit をAND演算（&）することで、i番目が1であれば選択するという処理が行われます。

まとめ

bit全探索は、多数の組み合わせを効率的に探索するための強力な手法です。
特に、全通りを計算することが難しい問題で、そのパフォーマンスの優位性を発揮します。
しっかりと理解し、問題に適用できるようにしましょう！

安定してC問題を解くのが目標！