7K12 blog

猫でも分かるアルゴリズム解説

ABC128 C - Switches

f:id:tkr987:20200625223812p:plain

https://atcoder.jp/contests/abc128/submissions/15677953

  • 制約が10しかないのでbit全探索する
  • ループの最後まで行けたらans++と書くと実装が楽。

f:id:tkr987:20200625223922p:plain

任意の電球1個について「配線を辿ってスイッチの個数のmod2がpかどうか」は O(10)で判定できる。電球が10個しかないので、任意のスイッチ1パターンに対して電球全て調べても O(10) \times 10 = O(100)で処理できる。

なお、スイッチがOFFのときはカウントしてはいけない。

if (NT_NyaaBit::Test(i, k) == e[k]) ++count;

と書きたくなるが、これだとスイッチOFFのときもカウントしてしまうため

if (NT_NyaaBit::Test(i, k) == 1 && e[k]) ++count;

と書く必要がある。スイッチパターンが全部で 2^{10}しかないので、全体計算量O(M2^N)で求まる。