問題概要

$N$ 本の鍵 $1, 2, \dots, N$ があり、それぞれ本物であるか、ダミーであるかのいずれかである。ドア X があり、鍵のうちの $K$ 本以上の本物が使用されると空く仕様となっている。

このドア X に対して、次の $M$ 回のテストを行った。 $i$ 回目のテストの内容は次の通りである。

$C_{i}$ 本の鍵 $A_{i, 1}, A_{i, 2}, \dots, A_{i, C_{i}}$ を使用したところ、ドアが開いたかどうかを確かめた ( $R_{i}$ が o ならば開き、x ならば開かなかった)。

このテスト結果に矛盾しないような、各鍵が「本物かダミーか」の組合せは何通りあるかを答えよ。

制約

$1 \le K \le N \le 15$
$1 \le M \le 100$

考えたこと

各鍵が本物かダミーかの組合せは全部で $2^{N}$ 通りある。ここで、 $N \le 15$ という制約を見よう。これはもう、「組合せを全部試してみよ」と言っているようなものだ。

よって、組合せを試すこととする。どの鍵が本物でどの鍵がダミーであるかを固定すれば、 $M$ 回のテストそれぞれについて、ドアが開くべきかどうかが判定できる。その結果が矛盾しないかどうかを確かめていけばよい。

計算量は $O(2^{N}M)$ となる。

コード

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

int main() {
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> A(M);
    vector<char> R(M);
    for (int i = 0; i < M; ++i) {
        int C;
        cin >> C;
        A[i].resize(C);
        for (int j = 0; j < C; ++j) {
            cin >> A[i][j];
            --A[i][j];
        }
        cin >> R[i];
    }
    
    long long res = 0;
    for (int bit = 0; bit < (1 << N); ++bit) {
        bool ok = true;
        for (int i = 0; i < M; ++i) {
            int num = 0;
            for (auto j : A[i]) {
                if (bit & (1 << j)) ++num;
            }
            if (num < K && R[i] == 'o') ok = false;
            if (num >= K && R[i] == 'x') ok = false;
        }
        if (ok) ++res;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 356 C - Keys (2Q, 茶色, 300 点)

問題概要

制約

考えたこと

コード