zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC128-C「Switches」です。
実装
#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;
}ポイント
今回おさえるべき内容
bit全探索の利用
良問です。bit全探索を利用する問題ですが，そう単純ではありません。それぞれの電球に繋がっているスイッチの個数が可変長なので，その個数を保持しておいてうまくforループに活かす必要がありました。また，0インデックスか1インデックスかを揃えなくてはならない点もあるので，C問題としてはかなり解きごたえのある問題だったのではないかと個人的には思っています。
コメント