Buying a Cellphone [第六回 アルゴリズム実技検定 C]

https://atcoder.jp/contests/past202104-open/tasks/past202104_c

解説

https://atcoder.jp/contests/past202104-open/submissions/22645364

たくさんの入力が与えられて、要求仕様を満たす実装ができるかを問う問題。
どんな実装をしても計算量が超えてしまうことは少ないだろう。
だが、実装の仕方によって楽になる方針もある。
自分の実装ではbitsetを活用した実装を行っている。
（どんな実装でも大丈夫です）

bitset解法

対応している周波数にbitを対応させ、ビットが立っていればその周波数に対応しているようにする。
A[i] := i番目の携帯電話についてj番目のビットが立っていればj番目の周波数に対応しているようなビットセット
以上のような定義のビットセットを作成して、Bについても同様のビットセットを作成しておく。

なぜbitsetを用いるかという部分であるが、A[i]とBのandを取って出てきたビットセットというのは、
A[i]にもBにもある周波数となり、これがちょうど数えるべき周波数となっている。
なので、A[i]とBのandを取り、立っているビットの数を数え、それがQ個以上であれば、買うべき携帯電話の候補の条件を満たす。
よって、全てのiについてA[i]とBのandを取って、ビットカウントしてQ個以上なら答えをインクリメントしていって数を数えていこう。

int N, M;
bitset<50> A[50];
int P, Q;
bitset<50> B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) {
        int K; cin >> K;
        rep(k, 0, K) {
            int a; cin >> a; a--;
            A[i].set(a);
        }
    }

    cin >> P >> Q;
    rep(i, 0, P) {
        int a; cin >> a; a--;
        B.set(a);
    }

    int ans = 0;
    rep(i, 0, N) {
        auto AandB = A[i] & B;
        if (Q <= AandB.count()) ans++;
    }
    cout << ans << endl;
}