[AtCoder] ABC 128 C – Switches

2019年5月26日

問題

方針

ビット全探索

制約を見ずにこの問題を解こうとすると、ドツボに嵌るかもしれません。スイッチの数と電球の数は最大でも \( 10 \) なので、全探索を考えます。スイッチの状態は on/off の \( 2 \) 通りなので、ビット全探索を用います。

例えば、スイッチが on のときを \( 1 \)、off のときを \( 0 \) と表します。スイッチの数が \( 3 \) 個のとき、スイッチの状態のパターンは、\( (0, 0, 0)\), \( (0, 0, 1)\), \( (0, 1, 0)\), \((1, 0, 0) \), \( (0, 1, 1)\), \( (1, 0, 1)\), \(( 1, 1, 0)\), \( (1, 1, 1)\) の \( 2^3 \) 通りあります。

実装

全体のスイッチの状態はビット列で表現できるので、ある電球に接続されているスイッチが on である個数を数え上げ、条件を満たすかどうか調べます。これを全ての電球に対して行います。

コード

提出したコード

ビット全探索と実装部分

int bit[10]{};
set<int> set0[10]{}; // 電球に接続しているスイッチ
int p[10]{};
int cnt = 0;

void solve() {
  for (int i = 0; i < M; i++) {
    int sum = 0;
    for (int j = 0; j < N; j++) {
      if (bit[j] == 1 && set0[i].count(j) == 1) sum++;
    }
    if (sum % 2 != p[i]) return;
  }
  cnt++;
}

void rec(int k) {
  if (k == N) {
    solve();
    return;
  }
  rec(k + 1);
  bit[k] = 1;
  rec(k + 1);
  bit[k] = 0;
}