【競プロ精進日記】ABC128-CBeginaid

本記事は管理人が競技プログラミングを始めたため，その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

概要

良問です！bit全探索を利用する問題ですが，そう単純ではありません。それぞれの電球に繋がっているスイッチの個数が可変長なので，その個数を保持しておいてうまくforループに活かす必要がありました。また，0インデックスか1インデックスかを揃えなくてはならない点もあるので，C問題としてはかなり解きごたえのある問題だったのではないかと個人的には思っています。

c++

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

int N=0, M=0, k=0;
long long ans=0;

int main(){
  cin >> N >> M;
  // 繋がっているスイッチを格納するベクター
  vector<vector<int>> S(M, vector<int>(N));
  // 各電球に繋がっているスイッチの個数を格納しておく配列
  int K[M];
  // 2で割ったあまりの条件を格納しておく配列
  int P[M];
  // 入力をそれぞれに格納していく
  rep(m, M){
    cin >> K[m];
    rep(i, K[m]){
      cin >> S[m][i];
    }
  }
  rep(m, M){
    cin >> P[m];
  }

  // ここからソルバー
  // bit全探索やる
  // まずは電球のONOFFを表すフラグを2^Nだけ考える
  rep(mask, 1<<N){
    bool flag[N];
    rep(n, N){
      if (mask & (1<<n)) flag[n]=true;
      else flag[n]=false;
    }

    // 全ての電球について2で割ったあまりがPの条件に等しいかどうかを保存するcheckフラグ
    bool check=true;

    rep(m, M){
      // ONの場所はtrueつまり1が格納されているのでインクリメントしていく
      int sum_flag = 0;
      rep(idx, K[m]){
        sum_flag += flag[S[m][idx]-1];
      }
      // Pの条件にあっているかどうかを判断
      if (sum_flag % 2 != P[m]) check=false;
    }
    // checkがいまだにtrueであれば全ての電球についてtureであったということ
    if (check) ans++;
  }
// 解答出力
cout << ans << endl;
}