bit全探索について

bit全探索とは

状態が2^n通りある問題に対して二進数をフラグに見立てる事で全探索をする方法です。
bit全探索では時間計算量がO(2^n)になるのでnの数が多いとTLEするのでnが少ない問題にしか使えません。

bit全探索のコードを書く上で必要な知識

for(int i = 0; i < (1<<n) i++){
}

if(i & (1<<j))

上のfor文は1を二進数表記とみなしてn回左シフトさせてるので0~2^n-1回までループします。
左シフトの動作は0001→0010→0100→1000と動いています。

下のif文はiを二進数表記で見た時に右から数えてj番目が1かどうかを判定します。

bit全探索をどう使うのか

実際にatcoder出てきた問題Train Ticketを使って解説します。

問題概要

4つの整数ABCDの間に+か-を入れて7に出来る式を出力しなさい。

問題解説

ABCDの間に+-を入れるかの選択が2^3しかないので、+-を入れるかどうかを01に置き換えてiを見ていく事でbit全探索が出来ます。入力が空白区切りではなく、ABCDと繋げられているのでまず文字列で受け取ってからint型のvectorに変換するとスムーズに実装できます。しかしこの問題は入力される数がn個ではなく、4個と決まっているのでbit全探索ではなくても手書きで条件分けする方法も使えます。（但しこの記事ではbit全探索の練習をする事が目的なのでbit全探索でコードを書きます）

ACコード

ABC079.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  vector<int>v(4);
  for(int i = 0; i < 4; i++)v[i] = s[i] - '0';

  for(int j = 0; j < (1 << 3); j++){
    int tmp = v[0];
    for(int k = 0; k < 3; k++){
      if(j & (1 << k))tmp += v[k+1];
      else tmp -= v[k+1];
    }
    if(tmp == 7){
      cout << v[0];
      for(int k = 0; k < 3; k++){
        if(j & (1 << k))cout << '+';
        else cout << '-';
        cout << v[k+1];
      }
      cout << "=7" << endl;
      return 0;
    }
  }
}

bit全探索中に答えを保持する変数tmpの初期値をv[0]にして、tmpに対してBCDを足すか引くかと実装すると簡単に書けます。
最後の計算式の復元は条件を=7の時に出力すれば良いのでstring等で1ループづつ保持しないで、条件を満たす時に上でやった動作を出力に置き換えて再度やるだけです。（最後の=7のし忘れに注意）

この記事を見てbitについて興味が沸いた人はAPG4bを見てビットの知識を深める事をおすすめします。