はじめに
応用力をつけるためにAtCoderを始めたが、せっかくなら強くなりたいので勉強している。その中でbit全探索があったのでABC 128 C-Switchesという問題で実装した。
この記事ではbit全探索のより簡単な応用例を見たのち、問題の回答記録に入っていく。
「bit全探索とは何なのか」ということに関しては、以下の記事が分かりやすかった。
bit全探索の使用例(部分和問題)
bit全探索の簡単な応用例として部分和問題が挙げられていた。
先に貼ったリンクでもC++の実装があったが、
私はC#で似たようなことをやった。
以下のコードは整数の配列numsから整数を選び、target = 11となる組み合わせを
虱潰しに探すという部分和問題である。
1つ目のfor文(のforの中身)で数値の選び方を決め、それに基づいて2つ目のfor文で数値を選び出し、その和がtargetと一致するか否かをチェックしている。
一致する組み合わせについては,で区切ってコンソールに出力する。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Practice
{
internal class Program
{
static void Main(string[] args)
{
int[] nums = { 1, 1, 2, 3, 5, 7, 9, 10};
int target = 11;
bool found = false;
// bitの値が100000000(=256)より小さい間繰り返す。
// bitは選び方のフラグの役割を果たす
for(int bit = 0; bit < (1 << nums.Length); bit++)
{
// 合計とリストの初期化
int sum = 0;
List<int> selected = new List<int>();
for (int i = 0; i < nums.Length; i++)
{
// 右からi番目のビットが1かどうか
if( ((bit>>i)&1) == 1 )
{
sum += nums[i];
selected.Add(nums[i]);
}
}
// targetと一致なら出力
if(sum == target)
{
Console.WriteLine(string.Join(", ", selected));
found = true;
}
}
if(found == false)
{
Console.WriteLine($"和が{target}になる変数の組はありません。");
}
}
}
}
1つ目のfor文で定義されるbitは、整数の選び方を示している。
例えば、bit = 37 = 0100101は1つ目の1、3つ目の2、6つ目の7を示す。
numsの順序と反対なことに注意。(2番目のfor文参照)
1 << nums.Lengthは1をnums.Length回左シフトした二進数を表す。
例えば1 << 3は1000となる。
また、101001 >> iは01001をi回右シフトした二進数を表す。
例えば101001 >> 2は001010となる。
上のコードでは(bit>>i)&1としているが、これは右シフトした数と00..1を
AND演算しているので、i番目のbitが1なら1、0なら0になる。
出力はこんな感じになる。2つある1は別物としてカウントされている。
このように、部分集合の上手い選び方を探す問題に対し、
bit全探索は効果的である。
ABC 128 C-Switches
このbit全探索を使って解ける問題として、ABC 128 C-Switchesが挙げられていた。
詳細な標準入力はリンク先参照。
初見で問題設定を呑み込むのに時間が要したので、
日本語多めで改めて説明を書いておく。
N個のスイッチとM個の電球があり、電球iはki個のスイッチに繋がれている。
電球iは、繋がっているki個のスイッチのうち、Onになっているスイッチが奇数個もしくは偶数個の時に点灯する。点灯条件が奇数個なのか偶数個なのかは電球によって異なる。
また、スイッチには1～NのIDが振られている。繋がっているスイッチの数とIDは電球によってそれぞれ異なるが、同じIDのスイッチに2つ以上電球が繋がっている場合もあるし、N個のうち電球が繋がっていないスイッチもあるかもしれない。
...そんな状況の下で、全ての電球が点灯するスイッチの状態はいくつあるか？というのがこの問題で問われていることだ。
誤答
初めはこんな風に回答した。しかしWAと判定された。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace C_Switches
{
internal class Program
{
static void Main(string[] args)
{
int answer = 0; // 答え(点灯できるパターン数)
int switchState = 0; // スイッチの状態
int bulbOn = 0; // 点灯している電球数
int[] countInput = Console.ReadLine().Split().Select(int.Parse).ToArray();
int countOfSwitches = countInput[0]; // スイッチの総数
int countOfBulb = countInput[1]; // 電球の総数
// 各電球がどのスイッチに繋がっているかの情報
int[][] bulbInfo = new int[countOfBulb][];
for (int i = 0; i < countOfBulb; i++)
{
bulbInfo[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
}
// 各電球の点灯条件
int[] modInput = Console.ReadLine().Split().Select(int.Parse).ToArray();
// 全てのスイッチの状態に対して調べる
for(switchState = 0; switchState < (1<<countOfSwitches); switchState++)
{
// 各電球についてアクセス
for(int i = 0; i < bulbInfo.Rank; i++)
{
// i番目の電球に繋がるスイッチのOn数
int sumOn = 0;
// 点灯フラグ
bool enlighten = false;
// 各電球が点灯するかチェック
for (int j = 1; j < bulbInfo[i].Length; j++)
{
if (modInput[i] == sumOn%2)
{
enlighten = true;
}
else if((switchState & (1<<bulbInfo[i][j])) == 1)
{
sumOn++;
}
else
{
enlighten = false;
}
}
// 電球がついていれば点灯電球数+1
if (enlighten)
{
bulbOn++;
}
}
// 全ての電球が付いたら答えをを+1
if(bulbOn == countOfBulb)
{
answer++;
}
}
Console.WriteLine(answer);
}
}
}
バグ(誤り)は以下の3つ。
-
bulbInfo.Rankを使っていること
ジャグ配列は次元が1なので、for(int i = 0; i < bulbInfo.Rank; i++)は1回しか回らない。つまり1つの電球についてしか検討されない。
正しくはbulbInfo.Length
-
(switchState & (1<<bulbInfo[i][j])) == 1におけるビットシフトのズレ
bulbInfo[i][j]は電球iが繋がっているスイッチのID(=1~N)を表している。しかし、例えばbulbInfo[i][j]=1の時、``1<<bulbInfo[i][j]は2進数で10となり2番目のスイッチを表すことになる。これでは検証したいスイッチとズレている。
正しくは(switchState & (1<<bulbInfo[i][j]-1)) == 1
-
bulbOnのリセット忘れ
bulbOnはプログラムの最初に0で初期化されて以降、増える一方になっている。
switchStateループの先頭でリセットしなければいけない。
正答
修正した回答は以下の通り。無事にACと判定された。
(途中から混乱してきたので、どさくさに紛れて変数名を変えたりしている。)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace C_Switches
{
internal class Program
{
static void Main(string[] args)
{
int answer = 0; // 答え(点灯できるパターン数)
int switchState = 0; // スイッチの状態
int enlightenCount = 0; // 点灯している電球数
int[] countInput = Console.ReadLine().Split().Select(int.Parse).ToArray();
int switchCount = countInput[0]; // スイッチの総数
int bulbCount = countInput[1]; // 電球の総数
// 各電球がどのスイッチに繋がっているかの情報
int[][] bulbInfo = new int[bulbCount][];
for (int i = 0; i < bulbCount; i++)
{
bulbInfo[i] = Console.ReadLine().Split().Select(int.Parse).ToArray();
}
// 各電球の点灯条件
int[] modInput = Console.ReadLine().Split().Select(int.Parse).ToArray();
// 全てのスイッチの状態を調べる
for (switchState = 0; switchState < (1 << switchCount); switchState++)
{
enlightenCount = 0; // 点灯数をリセット
// 各電球にアクセス
for (int i = 0; i < bulbInfo.Length; i++)
{
int switchOnSum = 0; // i番目の電球に繋がるスイッチのOn数
// 繋がっているスイッチのbitチェック
for (int j = 1; j < bulbInfo[i].Length; j++)
{
// s番目のbitはs-1回シフトでチェック
// ついていればスイッチのOn数を加算
if (((switchState >> (bulbInfo[i][j] - 1)) & 1) == 1)
{
switchOnSum++;
}
}
// 電球がついていれば点灯電球数+1
if (switchOnSum % 2 == modInput[i])
{
enlightenCount++;
}
}
// 全ての電球が付いたら答えをを+1
if (enlightenCount == bulbCount)
{
answer++;
}
}
Console.WriteLine(answer);
}
}
}
もっとスマートなやり方もありそうだが、今の私ではこれが限界だった。
しかしbit全探索についてはそこそこ分かったと思う。
Switchesの反省点
特にbulbOnのリセット忘れに表れているように、設計が甘いまま進めていたこと。
新しい概念に触れつつジャグ配列は初めて使いつつだったので、仕方のないことではあるがもう少し詰めてから書き出せば良かった。
bit全探索のひな型
大体こんな感じになると思う。問題設定によるアレンジは必須だろうけど。
for(int bit = 0; bit < (1<<選択対象の集合の要素数); bit++)
{
for(int i = 0; i < 選択対象の集合の要素数; i++)
{
if( bitをi回右シフトした最下位ビット値が1 )
{
iを選んでいた場合の処理
}
}
}
参考