ABC128 C - Switches

AtCoder Python3 bit全探索

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    S = [il()[1:] for _ in range(M)]
    P = il()

    ans = 0
    for i in range(1 << N):
        for m in range(M):
            cnt = 0
            for j in range(N):
                if i >> j & 1 and j+1 in S[m]:
                    cnt += 1
            if cnt % 2 != P[m]:
                break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

考え方

スイッチはONとOFFの2状態を持つ。
そのため、bit全探索によってすべてのスイッチのON, OFFパターンを網羅することが出来る。

for i in range(1 << N):によってスイッチの全パターンの探索を行っている。

    N = 2   # の場合（スイッチが２つ）
    1 << N  # は1の2ビット左シフト
    0001    # を2ビット左にシフトすると、
    0100    # になり、range(0100)の範囲は 0 ~ 3 となる。

    # つまり、
    0 => 0000   # 全てのスイッチがOFFの状態
    1 => 0001   # 1つ目のスイッチのみがONの状態
    2 => 0010   # 2つ目のスイッチのみがONの状態
    3 => 0011   # 1と2のスイッチがONの状態
    # と、すべてのスイッチのON,OFF状態のパターンを網羅することができる。

for m in range(M): でM個の電球を1つずつ探索し、

            for j in range(N):
                if i >> j & 1 and j+1 in S[m]:

で、スイッチのON, OFF と、電球にスイッチがつながっているか否かを判定している。

    i >> j & 1  # iのjビット右シフトを行い 理論積(&)でスイッチのON, OFF を判定している。
    # この場合の i は 全スイッチ種類のON, OFFパターン
    # j は スイッチの種類
    # i が 1, jが 0（1つ目のスイッチ）の場合、
    0001 >> 0000 => 0001    # となり、
    # 理論積で
    0001 & 1 = > 1 # となるので、jが0（1つ目のスイッチ）のとき、スイッチはONになっているとわかる。
    # あとは j+1 in S[m] で 電球m のスイッチリストにスイッチが存在するか否かを判定している。

スイッチがONになっている、かつ電球とスイッチがつながっている場合、
ONとなっているスイッチの数をカウントする。
あとはONになっているスイッチの個数を2で割った余りがpと等しいか否かを判定し、
条件に合うパターンをカウントすることで回答を得られる。