[Go] ビット全探索（AtCoder ABC147-C）

AtCoderの過去問をコツコツ解いています。
AtCoder Problemsを使って、Difficultyが茶色と緑色の問題を一問ずつ。コツコツと。

今日解いたABC147-C がビット全探索で解ける問題で、久しぶりにビット全探索を書くことになったので復習を兼ねてこちらにも記載。

ビット全探索

スイッチのON/OFFや、今回の問題のような正直者/不親切のような0/1で表せる状態を複数の対象に対して網羅的にチェックしたい時に使える方法です。
正直者/不親切な人間がN人いた場合の全パターンは2のn乗になります。それらをビットのパターンで表現し、網羅的にチェックすることができる方法になります。

実装例

ビットパターンを全網羅する処理は以下のように書けます。

func main() {
	n := 3
	for i := 0; i < (1 << uint(n)); i++ {
		fmt.Printf("%03b\n", i)
	}
}

実行結果は以下のようになり、3ビットの全パターンが網羅されていることがわかる。

000
001
010
011
100
101
110
111

初めてこの方法を知ったときに面白いと思ったのは、ループの上限を決める(1 << uint(n)) の部分です。やっていることは1をn回左にシフトしているということですが、こうすることでn個の1が並ぶビットパターンを持つ数値を取得でき、0がn個並ぶパターンである0から、インクリメントしていくことで全ビットパターンを網羅できます。こんなにシンプルに書けるのかと。

正直者か不親切な人かを知りたければ、各ビットに対して&を取って確認します。

func main() {
	n := 3
	for i := 0; i < (1 << uint(n)); i++ {
		fmt.Printf("%03b\n", i)
		for j := 0; j < n; j++ {
			if i>>uint(j)&1 == 1 {
				// ビットが立っていた場合の処理

			}
		}
	}
}

提出したコード

package main

import (
	"bufio"
	"fmt"
	"os"
)

type testimony struct {
	x int
	y int
}

func main() {
	r := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(r, &n)
	var a, x, y int
	ts := make([][]testimony, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(r, &a)
		testimonies := make([]testimony, a)
		for j := 0; j < a; j++ {
			fmt.Fscan(r, &x)
			fmt.Fscan(r, &y)
			testimonies[j] = testimony{x, y}
		}
		ts[i] = testimonies
	}

	ans := 0
	// bitで網羅してみる
	for i := 0; i < (1 << uint(n)); i++ {
		flg := true
		for j := 0; j < n; j++ {
			// 証言者が正直者かどうか
			honest := i>>uint(j)&1 == 1
			if !honest {
				// 不親切な人ならば証言のチェックはしない
				continue
			}
			for _, t := range ts[j] {
				if i>>uint(t.x-1)&1 != t.y {
					// 正直者の言う通りでなければまちがい
					flg = false
					break
				}
			}

			if !flg {
				break
			}
		}
		if flg {
			count := 0
			for j := 0; j < n; j++ {
				count += i >> uint(j) & 1
			}

			ans = max(ans, count)
		}
	}

	fmt.Println(ans)
}

// Utility

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}