【golang】Goでbit全探索をしよう

概要

先日、Goの勉強も兼ねて久しぶりにAtCoderの ABC147 に参加しました。

その際のC問題が bit全探索 を使用する問題だったのですが

• 実装をパッと思いつかない
• Goの文法知らない

で自分の貧弱さが浮き彫りとなってしまったので戒め(復習)のためbit全探索のGoでの実装をまとめます。

Goのbit演算

Goのbit演算は以下のような感じです:
参照: Goプログラミング言語仕様

const(
  A uint = 10   // 1010
  B uint = 12   // 1100
)

func main() {
  var bits uint
  
  // AND演算
  bits = A & B   // 1001
  // OR演算
  bits = A | B   // 1110
  // XOR演算
  bits = A ^ B   // 0110
  // AND NOT演算
  bits = A &^ B  // 0010
  // 左シフト演算
  bits = 1 << uint64(3) // 1000 : 2の3乗かかる
  // 右シフト演算
  bits = 8 >> uint64(3) // 0001 : 2の(-3)乗かかる
}

bit全探索とは

bit全探索については、ネットの海を探せばいくらでも出てくるので詳細は割愛します。

中学・高校数学で以下のようなことを習った記憶があるかと思います:

並べられた$n$個の要素がそれぞれ2つの状態を持つ場合、全パターン数は $2^{n}$ 通りある。

設問に出てくる一見複雑なシチュエーションを上記の考え方に当てはめることで
網羅的に全パターンを探索しようと試みるのがbit全探索のアルゴリズムの主旨です。

例

3種類のOS Linux, MacOS, Windows のうち好きなOSを選んでください。ただし、複数選択可能です。

上記の回答の全パターンを数えるときに、各OSに関して 好き/嫌い の２パターンが独立して存在するので $2^3 = 8$ 通りとなります。

実装パターン

bit全探索をプログラムで実装する場合は、基本的に以下のパターンになると思います。

var n int  // 独立な要素数

// bitsがn個の要素の各パターンを表す
for bits:=0;bits<(1<<uint64(n));bits++ {
  // bitsの各要素についてのループ
  for i:=0;i<n;i++ {
    // bitsのi個目の要素の状態がonかどうかチェック
    if (bits>>uint64(i))&1 == 1 {
      // 何かしらの処理
    }
  }
}

問題によってここから変形していくと思いますが
実装力をつけるためには型に慣れるというのは結構大事な気がします。

実装例

実際のコンテストで出題された問題に対して、bit全探索を利用した回答例を以下に示します。
(Goをビギナーのためクソコードな部分はぜひ指摘ください！)

問題

ABC128 C - Switches

回答

onとoffの2つの状態を持つ $N$ 個スイッチということで、全パターン数は $2^N$ 通りです。

$2^n$ 通り各パターンに対して、

1. 電球に繋がる各スイッチのビットの0/1をチェック(ビット演算を活用)
2. 点灯しない電球がある時点でbreakして次のループへ
3. 全電球が点灯する場合、count++

を行う実装となっています。

package main

import "fmt"

// Solve the problem of ABC128 C
func main() {
	var n, m int
	fmt.Scan(&n, &m)
	slist := make([][]int, m)
	for i := 0; i < m; i++ {
		k := 0
		fmt.Scan(&k)
		slist[i] = make([]int, k)
		for j := 0; j < len(slist[i]); j++ {
			fmt.Scan(&slist[i][j])
		}
	}
	plist := make([]int, m)
	for l := 0; l < m; l++ {
		fmt.Scan(&plist[l])
	}

	count := 0
	for bits := 0; bits < (1 << uint64(n)); bits++ {
		ok := true
		for j := 0; j < m; j++ {
			sum := 0
			for _, sNo := range slist[j] {
				sum += bits >> uint64(sNo-1) & 1
			}
			if sum%2 != plist[j] {
				ok = false
				break
			}
		}
		if ok {
			count++
		}
	}
	fmt.Println(count)
}

各電球主体に考えだすとパターンが複雑で混乱しますが、
スイッチの状態主体に考えると網羅的に探索できると思います。

ここら辺の発想は、bit全探索が使える問題をいくつか解くと勝手に身に付きます。
自分の場合、AtCoderの問題をユーザーの投票でカテゴリ分けする

AtCoder Tags - bit全探索

というサービスで似たような問題をまとめて解きました。便利！

まとめ

• Goでbit全探索を実装できるようになった
• bit演算の感覚をつかもう
• bit全探索を使えるシチュエーションに慣れよう