ABC128 C - Switches

問題はこちら atcoder.jp

方針

個のスイッチのon/off状態の順列は 通り，ということで一目全探索っぽいです。

問題では電球→スイッチの対応関係しか与えられないので，スイッチ→電球の対応関係を表す配列を作っています。あとはbit全探索です。

コード

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)

bool judge(int bit);

int n,m;
vector<int> k;
vector<vector<int>> s;
vector<int> p;
vector<vector<int>> stolb; // stolb[i]=j: スイッチiは電球jに接続する

int main(){
    cin>>n>>m;
    k.resize(m);
    s.resize(m);
    p.resize(m);
    stolb.resize(n);
    REP(i,m){
        cin>>k[i];
        s[i].resize(k[i]);
        REP(j,k[i]){
            // 電球iはスイッチs[i][j]-1と接続（添字のズレに注意）
            cin>>s[i][j];   
            // 逆に，スイッチs[i][j]-1は電球iと接続
            stolb[s[i][j]-1].push_back(i);   
        }
    }
    REP(i,m){
        cin>>p[i];
    }

    int count=0;

    for(int bit=0; bit<(1<<n); bit++){
        if(judge(bit)){
            count++;
        }
    }
   
    cout<<count<<endl;
}

bool judge(int bit){
    vector<int> on(m);
    REP(i,n){
        if(bit&(1<<i)){
            // スイッチiが接続する電球のonを+1（2で割った余りなので0→1か，1→0)
            REP(j,stolb[i].size()){
                if(on[stolb[i][j]]==0){
                    on[stolb[i][j]]=1;
                }else{
                    on[stolb[i][j]]=0;
                }
            }
        }
    }

    // 全て点灯しているか確認
    REP(i,m){
        if(on[i]!=p[i]){
            return false;
        }
    }

    return true;
}