ABC128 C Switches

出れなかったんだけど、AtCoderの解説動画が結構参考になったので、pythonで書く

数え上げ系すごく苦手なので、戒め兼補足。解説動画が少しわかりにくかったので。

問題概略。 ON/OFFスイッチが N 個と電球が M 個ある。それぞれのスイッチは複数の電球とランダムに接続されている。電球は、繋がっているスイッチのうちONになっているものの数が、偶奇どちらかの時(ランダム)、点灯する。それを決めるのは、P_i (1 ≦ i ≦ M)。全ての電球をつけるスイッチのパターンの数を求めよ。

解説では、bit全探索だった。N ≦ 10 なので、2 ^10 ≒ 10 ^3 なので十分。

まず、入力を表に接続表(隣接行列みたいなやつ)にする.

スイッチ番号\電球番号	0	1	2
0	1	1	0
1	1	0	1

こんな感じにしたい。bit全探索にすると、実装が楽になるので、2 進数にする。この時上の表と 桁が反転することになる。

スイッチ番号\電球番号	2 1 0
0	011
1	101

ここで、スイッチ 0 を押すと、それぞれの電球の押されているスイッチの数は

電球番号	2	1	0
押されているスイッチの数	0	1	1

になる。 さらに、スイッチ 1 を押すと

電球番号	2	1	0
押されているスイッチの数	1	1	2

こうなる。電球とスイッチが繋がっていない場合は、数は上がらず、スイッチを押すと、押したスイッチの接続表の行を足していく動作になる。

ここで、単純に押されているスイッチの数をそれぞれ 2 で割れば、あまりが出て、点灯しているかいないかがわかるが、単純に行を足すのではなく、排他的論理和をとれば、直接それぞれのあまりが出せて、実装が楽になる。

全探索の部分は、シフトを活かして、列挙する。1 が立っている桁と、スイッチのONが対応している具合に。

通った解答

def main():
    n, m = [int(i) for i in input().split()]
    # a[i] には i 番目のスイッチの 電球との接続情報が入っている
    a = [0 for i in range(n)]
    for j in range(m):
        k, *switch = [int(i) for i in input().split()]
        for s in switch:
            a[s-1] |= (1 << j)
    p = int(("".join(reversed([i for i in input().split()]))), base=2)

    ans = 0

    # bit全探索
    for i in range(1<<n):
        t = 0
        for j in range(n):
            if (i >> j & 1) == 1:
                t ^= a[j]
        if t == p:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()