極秘調査 [パソコン甲子園2015 予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0318?year=2015

考察仮定

1. 問題のベン図を見ながら高校数学のように数えやすい物をつかって表現する
2. すると答えはn(C) - n(A∧C) + n(A∧B∧C)となる
3. これを各々数えて、計算すると答え

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0318/judge/3140657/C++14

Nの制約が優しいので適当に判定できる。
n(A∧C)を計算するときは、「Aの中に頂点iがある∧Cの中に頂点iがある」の場合にインクリメントする。
n(A∧B∧C)も同様。
あとは、n(C) - n(A∧C) + n(A∧B∧C)が答え。

int N, X, A[101], Y, B[101], Z, C[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    cin >> X; rep(i, 0, X) cin >> A[i], A[i]--;
    cin >> Y; rep(i, 0, Y) cin >> B[i], B[i]--;
    cin >> Z; rep(i, 0, Z) cin >> C[i], C[i]--;

    int nc = Z;
    int nac = 0;
    rep(i, 0, N) {
        int ok = 0;
        rep(j, 0, X) if (A[j] == i) ok++;
        rep(j, 0, Z) if (C[j] == i) ok++;
        if (ok == 2) nac++;
    }
    int nabc = 0;
    rep(i, 0, N) {
        int ok = 0;
        rep(j, 0, X) if (A[j] == i) ok++;
        rep(j, 0, Y) if (B[j] == i) ok++;
        rep(j, 0, Z) if (C[j] == i) ok++;
        if (ok == 3) nabc++;
    }

    int ans = nc - nac + nabc;
    cout << ans << endl;
}