👏

【競技プログラミング】AtCoder Beginner Contest 128_C問題

に公開
競技プログラミング
tech

問題

https://atcoder.jp/contests/abc128/tasks/abc128_c

要約

  1. N個のスイッチ（on/offの状態を持つ）とM個の電球がある。

  2. スイッチには1からNまで、電球には1からMまでの番号がついている。

  3. 各電球iは以下の条件で点灯する

    • 電球iはk_i個のスイッチに接続されている。
    • これらのスイッチ（s_i1, s_i2, ..., s_ik_i）のうち、onになっているスイッチの数を2で割った余りがp_iに等しい時に点灯する。

  4. 全ての電球が同時に点灯するようなスイッチのon/offの組み合わせの数を求める問題。

変数情報：

  • N: スイッチの総数
  • M: 電球の総数
  • k_i: 電球iに接続されているスイッチの数
  • s_ij: 電球iに接続されているj番目のスイッチの番号
  • p_i: 電球iが点灯するための条件（onのスイッチ数を2で割った余り）

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

ビット全探索を用いて、全てのスイッチの組み合わせを生成し、各組み合わせに対して全ての電球が点灯するかどうかを確認する。
点灯条件を満たす組み合わせの数をカウントし、最終的な答えとする。

解法手順

  1. 入力を受け取り、必要なデータ構造を初期化する。
  2. 2^N通りのスイッチの組み合わせを生成するためのループを作成する。
  3. 各組み合わせに対して、全ての電球について以下を行う：
    a. 電球に接続されているスイッチのうち、ONになっているものの数を数える。
    b. ONになっているスイッチの数を2で割った余りが、その電球のp_iと一致するか確認する。
  4. 全ての電球が点灯条件を満たす場合、カウンターをインクリメントする。
  5. 全ての組み合わせを確認した後、カウンターの値を出力する。

ACコード

ac.py
def io_func():
    # スイッチの数Nと電球の数Mを入力として受け取る
    N, M = map(int, input().split())
    
    # 各電球に接続されているスイッチの情報を格納するリスト
    K = []
    S = []
    
    # M個の電球について、接続されているスイッチの情報を入力として受け取る
    for _ in range(M):
        data = list(map(int, input().split()))
        K.append(data[0])  # 接続されているスイッチの数
        S.append(data[1:])  # 接続されているスイッチの番号リスト
    
    # 各電球の点灯条件を入力として受け取る
    P = list(map(int, input().split()))
    
    return N, M, K, S, P

def solve(N, M, K, S, P):
    ans = 0  # 条件を満たすスイッチの組み合わせの数
    
    # 2^N通りのスイッチの組み合わせを生成
    for i in range(1 << N):
        all_lights_on = True  # 全ての電球が点灯しているかどうかのフラグ
        
        # 各電球について点灯条件を確認
        for j in range(M):
            on_switches = 0  # ONになっているスイッチの数
            
            # 電球に接続されている各スイッチの状態を確認
            for switch in S[j]:
                if i & (1 << (switch - 1)):  # スイッチがONの場合
                    on_switches += 1
            
            # 点灯条件を満たしているか確認
            if on_switches % 2 != P[j]:
                all_lights_on = False
                break
        
        # 全ての電球が点灯条件を満たしている場合、カウンターをインクリメント
        if all_lights_on:
            ans += 1
    
    return ans

if __name__=="__main__":
    # メイン処理
    N, M, K, S, P = io_func()  # 入力を受け取る
    result = solve(N, M, K, S, P)  # 問題を解く
    print(result)  # 結果を出力

###
# - N: スイッチの数
# - M: 電球の数
# - K: 各電球に接続されているスイッチの数のリスト
# - S: 各電球に接続されているスイッチの番号のリストのリスト
# - P: 各電球の点灯条件（ONのスイッチの数を2で割った余り）のリスト
# - ans: 条件を満たすスイッチの組み合わせの数

# 1. io_func関数:
#    - 標準入力から問題のパラメータを読み込む
#    - スイッチの数N、電球の数M、各電球の接続情報K,S、点灯条件Pを返す
# 2. solve関数:
#    - ビット全探索を用いて、2^N通りのスイッチの組み合わせを生成
#    - 各組み合わせに対して、全ての電球が点灯条件を満たすか確認
#    - 条件を満たす組み合わせの数をカウントし、最終的な答えとして返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く
#    - 結果を出力する

覚書

入力例3のケース

N, M = 5,2
K = [3,2]
S = [[1,2,5],[2,3]]
P = [1,0]

forループ

for i in range(1 << N):

0～31までループ(range(2^5))

電球に接続されている各スイッチの状態を確認

# 電球に接続されている各スイッチの状態を確認
for switch in S[j]:
    if i & (1 << (switch - 1)):  # スイッチがONの場合
        on_switches += 1

例えば、i=6:(00110)の場合
スイッチ1: ●●●〇● →1個点灯
スイッチ2: ●●〇〇● →2個点灯

例えば、i=23:(10111)の場合
スイッチ1: 〇●●〇〇 →3個点灯
スイッチ2: ●●〇〇● →2個点灯

例えば、i=24:(11000)の場合
スイッチ1: 〇●●●● →1個点灯
スイッチ2: ●●●●● →0個点灯

となり、条件を満たす。

Discussion