zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC147-C「HonestOrUnkind2」です。
ポイント
ややこしい問題でした。ポイントは，不親切な人は嘘をつくわけではないということです。不親切な人の証言は真なのか偽なのか判断できないため，無視してOKというのがこの問題のキモになります。
方針としては，$N$が大きくないためbit全探索を利用して$N$人の人が「正直者」か「不親切な人」のどちらなのかを仮定して，その都度証言同士が矛盾していないかどうかを確かめます。矛盾しないケースで，正直者が一番多いパターンを正解として出力します。bit全探索については，以下の記事をご覧ください。
あわせて読みたい
【c++で楽しく実装！】bit全探索
本記事では，bit全探索の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください。 目次へジ...
おさえるべき内容
bit全探索の使い方
実装
#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 main(){
int N;
int A[20];
int X[20][20];
int Y[20][20];
cin >> N;
rep(i, N){
cin >> A[i];
rep(j, A[i]){
cin >> X[i][j];
X[i][j]--;
cin >> Y[i][j];
}
}
// ここからソルバー
int ans = 0;
// bit全探索していく
// とりあえずN人の人がそれぞれ正直者か不親切な人かを仮定するflagを作ってしまう
rep(mask, 1<<N){
bool flag[N];
rep(n, N){
if (mask & (1<<n)) flag[n]=true;
else flag[n]=false;
}
// 矛盾がおきていないかをチェックするflag
bool check = true;
// 実際に矛盾がないかチェックしていく
rep(i, N){
// 不親切な人の場合は無視する
if (flag[i]==false) continue;
// 実際の証言Yと仮定flagを比較して正直者なはずなのに間違えていれば矛盾フラグをfalseにする
rep(j, A[i]){
if (Y[i][j] != flag[X[i][j]]) check = false;
}
}
// 正直者が何人いるか数え上げるする変数
int sums = 0;
if (check == true){
rep(i, N) sums += flag[i];
// ansを更新していく
ans = max(ans, sums);
}
}
// 出力
cout << ans << endl;
}
コメント