abc128cのノート

概要

今までbitFlagをしたり普通に計算として二進数を扱う問題が数多くあったが今まで解けずじまいだった。

ここで練習したので、次に生かしたい。

今回は先人のコードを読み解いたというメモ。

二進数の演算について

今回使ったのがアンド演算子。 出力は普通の掛け算となる。

bitFlagは、組み合わせの全列挙を行う際に掛け合わせの金型として使うと丁度良い。

今回の問題だとオンを1、オフを0として扱うとスイッチsの組み合わせを各桁で表すことが可能になる。

桁の繰り上げは左シフトが適当で、二進数のbitFlagの作り方もこれで二進数で桁数指定でき簡単になる。

入力のnがスイッチの数すなわちn桁分bitFlagを用意すれば十分なので

range(1<<n)

とすると、2ⁿ-1の数(11111 11111)までを指定できる。

abc128c

atcoder.jp

解説にある通り、全列挙をすると計算量がO(mn*2ⁿ)となるので2¹⁰を大分多く見積もって概算10⁴としてもオーダー全体で10⁶で間に合う（らしい）

パクったコード

今回は完全にパクりコード。

毎度読みやすくて理解がしやすい。

一番深いインデントのアンド計算の左シフトでs-1としているのは、スイッチの番号が1から始まるのに対して桁数の表現が2⁰から始まりシフトの必要性がないのでその整合のためである。

# original_author prd_xxx

N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
# 2^Nまでrange探索を行う。
for b in range(1<<N):
    for i in range(M):
        c = 0
        for s in src[i][1:]:
            if b&(1<<(s-1)):
                c += 1
        # 最後に条件スイッチの条件と合致しているか検証
        # 合わなければelseに飛ばずbの次を検証しに行く
        if c%2 != P[i]: break
    else:
        ans += 1
print(ans)