記事にした背景

Atcoder（JavaScript）で挑戦中にbit全探索に出会ったのですが、まったく手が出せなかったので、勉強がてら記事にしました。

参考にさせていただいた記事

@u2dayo様の以下の記事を参考にさせていただきました。

1. 入門編 bit全探索ってなに？

bit全探索とは？

参考にさせていただいた記事の1. 入門編 bit全探索ってなに？によると、以下のように記述されています。

『ありえる選択肢の組み合わせ方を全てもれなく列挙』して、『一つ一つの組み合わせに対して計算や判定を行う』ことで、答えを見つけるアルゴリズム

ただし、制約として以下も記述されています。

bit全探索は、選択肢の数 $N$が比較的小さいときでないと使えません。

処理の複雑さにもよりますが、$N≤20$が実行時間制限に余裕を持ってbit全探索を使える目安です。

では、実際にbit全探索を使用して例題を解いてみましょう。

例題

$N = 1,3,4$のとき、Nの部分集合の合計$S$が$S = 4$となる部分集合はいくつあるか？

解き方

すべての部分集合を求める。
空集合$, ｛1｝, ｛3｝, ｛4｝, ｛1, 3｝, ｛1, 4｝, ｛3, 4｝, ｛1, 3, 4｝$
1のうち$S = 4$となるものを求める。
$｛4｝, ｛1, 3｝$

以上の通り、$2$が解となります。

アルゴリズムを考える

1. すべての部分集合を求める。

ここでは2進数を使用して考えてみます。0を使用しない、1を使用するとして以下の表をご覧ください。

1	3	4	部分集合
0	0	0	空集合
0	0	1	{4}
0	1	0	{3}
0	1	1	{3, 4}
1	0	0	{1}
1	0	1	{1, 4}
1	1	0	{1, 3}
1	1	1	{1, 3, 4}

すると使用するNの個数が3なので、3桁の2進数ですべての部分集合の組み合わせを求めることができます。

では、3桁の2進数の組み合わせを求めるコードを以下に記述します。

function calcAllC(){
    newBox = [];
    for(let i = 0; i < (1 << 3); i++){
        newBox.push(i.toString(2).padStart(3, '0'));
    }

    console.log(newBox);

}

1 << 3 は1を左に3シフトする
.toString(2)は2進数表記に変換する（ただし文字列になる）
.padStart(3, '0')は3桁になるよう0で埋める
という意味です。

この関数を呼び出すと以下のように出力されます。

[
  '000', '001',
  '010', '011',
  '100', '101',
  '110', '111'
]

2. 1のうちS = 4となるものを求める。

1で求めた組み合わせを1件ずつ取り出し、処理します。1の場合は仮の合計値に足します。例えば、取り出した組み合わせが「110」の場合は、1x1 + 1x3 + 0x4となります。最後に$S$と一致すれば$count$の値を1増やします。

   
   // すべての2進数の組み合わせを1つずつ処理する
   for(target of allC){
        targetC = target.split(/(?!$)/u);
        sum = 0;

        // 2進数の組み合わせを1桁ずつ処理する
        for(let j = 0; j < targetC.length; j++){
            // 1(使用する)の場合はsumに足す
            if(targetC[j] === "1"){
                sum += nums[j];
            }
        }
        // （すべての桁の足し算が終わり、）sumの値が4の場合はcountに1を足す
        if(sum === targetSum){
            count++;
        }
   }

最終的なコード

function Main(input){
  
   targetSum = 4;
   nums = [1, 3, 4];
   allC = calcAllC();

   count = 0;
   
   // すべての2進数の組み合わせを1つずつ処理する
   for(target of allC){
        targetC = target.split(/(?!$)/u);
        sum = 0;

        // 2進数の組み合わせを1桁ずつ処理する
        for(let j = 0; j < targetC.length; j++){
            // 1(使用する)の場合はsumに足す
            if(targetC[j] === "1"){
                sum += nums[j];
            }
        }
        // （すべての桁の足し算が終わり、）sumの値が4の場合はcountに1を足す
        if(sum === targetSum){
            count++;
        }
   }

   console.log(count);

}

function calcAllC(){
    newBox = [];
    for(let i = 0; i < (1 << 3); i++){
        newBox.push(i.toString(2).padStart(3, '0'));
    };

    return newBox;
}

// Main関数の実行
Main(require("fs").readFileSync("/dev/stdin", "utf8"));