ABC128C- Switches

ABC128C - Switches

解けた!!うれしい！！

問題

提出AC

#include <bits/stdc++.h>

using namespace std;
using ll =long long;

#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cout << #x << " = " << (x) << endl;
bool coY() {cout <<"Yes"<<endl;}
bool coN(){cout <<"No"<<endl;}

const ll INF = 1LL << 60;

ll n,m,h,w,k,a,b;
string s;
//Write From this Line

int main()
{
    cout << setprecision(10);

    cin >> n  >> m;
    //電球がk個のスイッチにつながってるって考えるよりも、あるスイッチは電球kにつながっている。って考えたほうがよさそう。
    //i番目のスイッチを押したらk番目のスイッチに＋1する。みたいな感じにしたい。
    map<int,vector<int>> Swi;
    rep(i,m){//m個の電球に関する情報が与えられる。
        cin >> k ;
        rep(j,k){//電球i+1は、k個のスイッチと繋がっている。
            cin >> a ;
            a--;
            Swi[a].push_back(i);
        }
    }
    rep(i,n){
        if(!Swi.count(i)){
            Swi[i].push_back(-1);//i番目のスウィッチを押しても何も起こらないなら-1を入れておこう
        }
    }
    vector<int> p(m);
    rep(i,m){
        cin >> p[i];
        //電球iは、繋がっているスイッチの個%2 == p[i]のときに光る
    }
    
    //ここまでが入力
    
    //bit数がスイッチの数、スイッチが5個なら00000から11111までで全探索
    //01010なら2個目のスイッチと4個目のスイッチ(Swi[2]とSwi[4]を見て、Swi[2]に入っている要素（電球）の値を＋1する。みたいな処理
    ll ans = 0 ;
    for(int tmp = 0 ; tmp < ( 1 << n); tmp++){
        bitset<10> bit(tmp);
        vector<int> count(m,0);
        //debug(bit);
        for(int i = 0 ;i<n; i++){
            if(bit.test(i)){
                //i番目のビットが経っているなら、Swi[i]の中身を見る.
                for(auto x : Swi[i]){
                    if(x==-1){
                        continue;
                    }
                    count[x] ++;
                }
            }
        }
        //countに、それぞれの電球が何個押されてるかが入っている
        bool flag = true;
        for(int i = 0 ; i < m ; i ++){
            if(count[i] % 2 == p[i]){
                // ok
            }else{
                flag = false;//点灯してないやつが見つかったのでfalse にしてbreak
                break;
            }
        }
        if(flag){//全部点灯
            ans ++ ;
        }
        //debug(ans);
    }
    cout << ans << endl;
}

解法

i番目の電球はあのスイッチとこのswitchを推したら光る。っていう情報は使いずらいので、

i番目のswitchは、これとあれとそれにつながってる。みたいな情報にする

ex) switch[i] = {電球1,電球3,電球5}みたいな感じ

スイッチは10個で、それぞれのスイッチについてon かoff なので2¹⁰ 通り、1024通りについて、全部が点灯するか。なのでまあ多分計算量気にしなくても実装出来ればきっと通る！！っていう期待を込めながらコードを書くとACできる。

switch[i] = { 1, 3 , 5}みたいなものを作れたら、だいぶ見通しが良くなる。

スイッチの数に対応すbitを用意する

スイッチが5個のとき

bit が00000なら、すべてのswitchがoff

★10101なら、0番目と2番目と4番目のスイッチがon

って感じで、★

のとき、switch[0],switch[2],switch[4]の中を見る。

で、みた結果に対してすべてが点灯するかどうかを判定する！！

ちなみに

解説のXORを使う解法はよくわからなかった…

この問題、前から難しそう!!って思って避けてた問題だけど、

難しいからこそやらなきゃダメだろ！！ってことで挑戦してみました！！

解けてうれしいです！！（今日は11/29）