【AtCoder】ABC 356 B - Nutrients | 茶コーダーが解くAtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 568

問題概要

$N$ 本の鍵があり、そのうち何本かは正しい鍵で、残りはダミーの鍵である。また、鍵を何本でも挿し込めるドア X があり、このドアは正しい鍵を $K$ 本以上挿し込んだときに限って開く。あなたはこれらの鍵に対して $M$ 回のテストを行った。 $i$ 回目のテスト内容は以下の通り。

$C_i$ 本の鍵 $A_{i, 1}, A_{i, 2}, \cdots, A_{i, C_i}$ をドア X に挿し込む。
テスト結果は英小文字 $R_i$ で表され、oのときはドアが開いたことを、xのときはドアが開かなかったことを表す。

各鍵が正しいかダミーかの組み合わせは $2^N$ 通り存在するが、このうちどのテスト結果にも矛盾しない組み合わせの個数を求めよ。ただし、与えられるテスト結果が誤っており、上記の条件を満たす組み合わせが存在しない場合もあるので、そのときは $0$ と解答せよ。

制約

$N, M, K, C_i, A_{i, j}$ は整数。
$R_i$ はo, xのいずれか。
$1 \leq K \leq N \leq 15$
$1 \leq M \leq 100$
$1 \leq C_i, A_{i, j} \leq N$
$A_{i, j}$ は相異なる。

考察

注目すべきは $N, M$ の制約の小ささだ。 $2^{15} = 32768$ なので、求めるべき組み合わせの個数は、全ての組み合わせに対して $M$ 回のテスト結果と矛盾しないかをチェックするという全探索で求められるだろう。

こういうときはbit全探索が有効である。 $N$ 桁のビット列を考え、 $i$ 本目の鍵が正しい鍵ならばビット列の $i$ 桁目を $1$ にする (ただし、この $i$ は 0-indexed) 。逆にダミーの鍵ならば $0$ にする。こうすることで、全てのパターンを2進数を用いて列挙することが可能だ。

次にテスト結果と矛盾する組み合わせの条件について考えよう。

ある組み合わせについて、テスト $i$ で使った鍵の中で正しい鍵の個数を $t_i$ とする。 $R_i$ がoのときは、 $t < K$ ならば、ドアが開いているのに実際には必要な正しい鍵の数が足りていないことから矛盾。一方、 $R_i$ がxのときは、 $t \geq K$ ならば、正しい鍵の数は足りているはずなのに実際にはドアが開いていないので矛盾する。

この条件を通過した組み合わせの個数を数えていけばよい。

実装にあたっては、bit全探索特有の表現を使う必要があるので慣れないと難しいかもしれない。この辺りに関しては以下の記事が詳しい。そのうち自分でも書くかもしれない。

drken1215.hatenablog.com

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<int>> A(M);
    vector<char> R(M);
    rep(i, 0, M)
    {
        int C;
        cin >> C;
        A[i].resize(C);
        rep(j, 0, C) cin >> A[i][j];
        cin >> R[i];
    }

    int ans = 0;
    rep(bit, 0, (1 << N))
    {
        bool flag = true;
        rep(i, 0, M)
        {
            int count = 0;
            for (auto &&key : A[i])
            {
                if (bit & (1 << (key - 1)))
                    count++;
            }

            if ((R[i] == 'o' && count < K) || (R[i] == 'x' && count >= K))
            {
                flag = false;
                break;
            }
        }

        if (flag)
            ans++;
    }

    cout << ans << endl;
    return 0;
}