記事にした背景
Atcoder（JavaScript）で挑戦中にbit全探索に出会ったのですが、まったく手が出せなかったので、勉強がてら記事にしました。
参考にさせていただいた記事
@u2dayo様の以下の記事を参考にさせていただきました。
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"));