ビット全探索の問題にハマる
ビット全探索の勉強のためにABC128のC問題に挑戦しました。
まずは念のために計算量の計算。スイッチの数が10個なので、それぞれのスイッチが消えているか、ついているかを全部列挙しても2**10 = 1024通り。
電球の数も最大で10で、それぞれの電球が点灯しているかチェックするためのスイッチのパターンも最大で10通り。
ざっくりと1024 * 10 * 10 = 102400なので、まぁ全然大丈夫なオーダーだなと思って、サラサラと書いたのですがバグを埋め込んでしまい、1時間もバグを見つけるのにかかってしまいました。。。
原因はインプットのスイッチの番号は1番から始まるのに対して、スイッチの位置に対応したビットシフトをするときに1つ多めにビットシフトしていました。
インプットのスイッチの位置を-1して解消したのですが、デバッガで数字見てても思い込みがあったのかなんなのか、気づけませんでした。
なんだかなぁ。。。
N, M = list(map(int, input().split())) s_arr = [] count = 0 for _ in range(M): kss = list(map(int, input().split())) s_arr.append(kss[1:]) p = list(map(int, input().split())) for bit in range(1 << N): all_bright = True for i, s in enumerate(s_arr): c = 0 for ss in s: if bit & (1 << (ss - 1)): c += 1 if c % 2 != p[i]: all_bright = False break if all_bright: count += 1 print(count)