【AtCoder】ビット演算

ポイント

ビット全探索

for (int i = 0; i < (1 << N); i++) {
  for (int j = 0; j < N; j++) {
    if ((i >> j) & 1) { ~ }
  }
}

その他のビット演算

下記は、配列の各要素の数値をXとした時に、ビット列のX桁目の値を1に変換した時の対応する整数値を出力する実装例です。

vector<int> v = { 1, 4, 5 };
int ans = 0; // 対応するビット列
for (int x : v) ans |= (1 << (x - 1));
cout << ans << endl;

例題

ABC289C - Coverage

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)

int main() {
  int N, M; cin >> N >> M;
  vector<int> L(M, 0);
  rep(i, M) {
    int cnt; cin >> cnt;
    rep(j, cnt) {
      int a; cin >> a;
      L[i] |= (1 << (a - 1));
    }
  }
  
  int ans = 0;
  rep(i, (1 << M)) {
    int total = 0;
    rep(j, M) {
      if ((i >> j) & 1) total |= L[j];
    }
    if (total == (1 << N) - 1) ans++;
  }
  cout << ans << endl;
}