問題
要約
- N個のスイッチ（on/off状態を持つ）とM個の電球がある。
- スイッチには1からN、電球には1からMの番号がついている。
- 各電球iは以下の条件で点灯する：
- ki個のスイッチに接続されている
- 接続されたスイッチのうち、onになっているスイッチの数を2で割った余りがpiに等しい時
- 全ての電球が同時に点灯するようなスイッチのon/offの組み合わせの数を求める。
変数情報：
- N: スイッチの総数
- M: 電球の総数
- ki: 電球iに接続されているスイッチの数
- si1, si2, ..., siki: 電球iに接続されているスイッチの番号
- pi: 電球iが点灯するための条件（接続されたスイッチのon数を2で割った余り）
既存投稿一覧ページへのリンク
アプローチ
ビット全探索を用いて、全てのスイッチの組み合わせを効率的に生成し、各組み合わせに対して全ての電球の点灯条件を確認する。
- 全ての可能なスイッチの組み合わせを調べる必要があるため、ビット全探索を使用。
- 各組み合わせに対して、全ての電球の点灯条件を確認する。
そのため、二重ループ構造（ビット全探索のループと電球の確認ループ）を使用。
解法手順
-
入力を受け取る：
- スイッチの数Nと電球の数Mを取得する
- 各電球に接続されているスイッチの情報を2次元リストとして保存する
- 各電球の点灯条件pを取得する
-
ビット全探索を実行する：
- 0から2^N-1までの数をビットパターンとして使用する
-
各ビットパターンに対して以下の処理を行う：
- オンになっているスイッチのリストを作成する
- 全ての電球に対して点灯条件を確認する：
- 電球に接続されているスイッチのうち、オンになっているものの数を数える
- その数を2で割った余りが点灯条件pと一致するか確認する
- 全ての電球が点灯条件を満たす場合、カウンターをインクリメントする
-
全てのパターンをチェックした後、カウンターの値を出力する
ACコード
ac.py
def io_func():
# スイッチの数Nと電球の数Mを取得
n, m = map(int, input().split())
# 各電球に接続されているスイッチの情報を2次元リストとして保存
lights = [list(map(int, input().split()))[1:] for _ in range(m)]
# 各電球の点灯条件pを取得
p = list(map(int, input().split()))
return n, m, lights, p
def solve(n, m, lights, p):
res = 0 # 条件を満たす組み合わせの数をカウントする変数
# ビット全探索を実行
for bit in range(1 << n):
light_on = [] # オンになっているスイッチのリスト
# オンになっているスイッチを特定
for i in range(n):
if (bit >> i) & 1:
light_on.append(i + 1)
flag = True # 全ての電球が条件を満たすかどうかのフラグ
# 全ての電球に対して点灯条件を確認
for i in range(m):
cnt = 0 # オンになっているスイッチの数
for light in lights[i]:
if light in light_on:
cnt += 1
# 点灯条件を満たしているか確認
if cnt % 2 != p[i]:
flag = False
break
# 全ての電球が条件を満たす場合、カウンターをインクリメント
if flag:
res += 1
return res
# メイン処理
n, m, lights, p = io_func()
result = solve(n, m, lights, p)
print(result)
###
# 変数の意味:
# n: スイッチの数
# m: 電球の数
# lights: 各電球に接続されているスイッチの情報を格納した2次元リスト
# p: 各電球の点灯条件を格納したリスト
# res: 条件を満たす組み合わせの数
# bit: ビット全探索に使用する変数
# light_on: 現在のビットパターンでオンになっているスイッチのリスト
# flag: 全ての電球が条件を満たすかどうかを示すフラグ
# cnt: 各電球に対して、オンになっているスイッチの数
# 1. io_func関数で入力を受け取る
# 2. solve関数で主な処理を行う
# - ビット全探索を使用して全てのスイッチの組み合わせを生成
# - 各組み合わせに対して、全ての電球の点灯条件を確認
# - 条件を満たす組み合わせの数をカウント
# 3. 結果を出力する
####################################################################################
# このコードの計算量は O(2^N * M * K)
# - N はスイッチの数
# -- ビット全探索で 2^N 回のループを行います。
# - M は電球の数
# -- 各ループで M 個の電球をチェックします。
# - K は各電球に接続されているスイッチの平均数
# -- 各電球のチェックで平均 K 個のスイッチを確認します。
####################################################################################
解法整理
-
集合論と組み合わせ論
- スイッチの集合 S = {1, 2, ..., n} を考える。
- 全ての可能なスイッチの組み合わせ（部分集合）を探索している。
- これは $2^n$ 通りの組み合わせを意味する。
-
二進法（2進数）とビット演算
-
for bit in range(1 << n):の部分で、0から $2^n - 1$ までの数を2進数で表現している。 -
1 << nは $2^n$ を表す。これは1を2進数で左に n ビットシフトすることで得られる。 -
(bit >> i) & 1の部分で、bit の i 番目のビットが1かどうかを判定している。-
bit >> iは bit を右に i ビットシフトする操作。 -
& 1は最下位ビットとの論理積を取る操作。
-
-
-
剰余演算（偶奇判定）
-
cnt % 2 != p[i]の部分で、オンになっているスイッチの数の偶奇を判定している。 - $a \equiv b \pmod{2}$ という合同式で表現できる。
-
-
論理演算
-
flag変数を使用して、全ての条件を満たすかどうかを論理的に判定している。 - これは $\land$ (AND) 演算子を用いて $\bigwedge_{i=1}^m (条件_i)$ と表現できる。
-
-
2次元配列（行列）
-
lightsは $m \times k_i$ の2次元配列（ただし $k_i$ は各行で異なる可能性がある）。 - これは数学的には $m$ 個の集合 $L_i \subseteq S$ $(i = 1, 2, ..., m)$ と考えられる。
-
-
計数問題
- 条件を満たす組み合わせの数を数え上げている。
- これは $|{x \in \mathcal{P}(S) : 条件(x)}|$ と表現できる。ここで $\mathcal{P}(S)$ は S のべき集合。
-
時間計算量
- このアルゴリズムの時間計算量は $O(2^n \cdot m \cdot \bar{k})$ である。
- $\bar{k}$ は各電球に接続されているスイッチの平均数。
ループ変数とビット演算の説明
-
外側のループ
for bit in range(1 << n):は、0から $2^n - 1$ までの全ての整数を生成する。
各整数bitは、n個のスイッチのオン/オフの状態を表す。 -
内側のループ
for i in range(n):は、各スイッチの状態を確認する。
(bit >> i) & 1の操作で、i番目のスイッチがオンかオフかを判定する。-
bit >> iはbitを2進数表記で右に i ビットシフトする。これにより、i番目のビットが最下位ビットになる。 -
& 1は最下位ビットとの論理積を取る。結果が1ならそのスイッチはオン、0ならオフとなる。
-
-
light_onリストには、オンになっているスイッチの番号が格納される。
これにより、各ビットパターンに対応するスイッチの組み合わせが得られる。