[AtCoder] ABC 147 C – HonestOrUnkind2

2019年12月9日

問題

方針

ビット全探索

ある人は正直者か不親切な人かの \( 2 \) 通りなので、全体で \( 2^N \) のパターンがあります。なので、ビット全探索を行います。人 \( i \) が正直者としたとき、その証言が現在のビットの状態と同じかどうかを調べることで最大値を求めることができます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int ans = 0;
int N;
int A[15], x[15][15], y[15][15];
int bit[15]{};

void solve() {
    int t = 0;
    for (int i = 0; i < N; i++) {
        if (bit[i] == 1) t++;
    }
    for (int i = 0; i < N; i++) {
        if (bit[i] == 0) continue;
        for (int j = 0; j < A[i]; j++) {
            if (bit[x[i][j]] != y[i][j]) return;
        }
    }
    ans = max(ans, t);
}

void rec(int k) {
    if (k == N) {
        solve();
        return;
    }
    rec(k + 1);
    bit[k] = 1;
    rec(k + 1);
    bit[k] = 0;
}

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        for (int j = 0; j < A[i]; j++) {
            cin >> x[i][j] >> y[i][j];
            x[i][j]--;
        }
    }
    rec(0);
    cout << ans << "\n";
    return 0;
}