ABC 128 C - Switches

atcoder.jp ABC147-C,ABC159-Eについで3度目のbit全探索が題材

初手の方針

N,Mが最大で10なのでスイッチのon/offパターンは全列挙しても,それぞれの電球が繋がるスイッチを1つずつ走査してもで余裕で間に合いそうということで全探索することにした。

[WIP] 正答

bit演算は奥が深いので別の記事でまとめようと思う。 まだまだ計算量減らす余地がありそう。

Submission #12232743 - AtCoder Beginner Contest 128

振り返り

理解していれば毎回スクラッチで書いてもいいと思ってたけどテンプレあったほうが変な事故がなさそうで良いなと思った。

  for(ll bit =0; bit < (1<<n); bit++) {
    for(ll i =0; i < n; i++) {
      if(bit & (1 << i)) {
        cout << 1 << " ";
      } else {
        cout << 0 << " ";
      }
    }
    cout << endl;
  }