Atcoder初心者学習① ビット全探索 【競プロ典型90問 002】

問題

bit全探索

本問題の場合、N文字の中で使用可能な文字は"("と")"のみなので、0と1のみの1bitで表現できる。

例.
((()))→000111
()()()→010101

このときN文字の全組み合わせは$2^N$通り存在する。これを素直に実装しようとすると

for(int i_0=1; i_1<=1; i++){
      for(int i_2 =0; i_2<=1; i++){
         /*・・・*/
               for(int i_N = 0; i_N<=1; i++){
                   a = i_0*10000000... + i_1*1000000... +/* ・・・*/ + i_N-1*10 + i_N;
                }
       }
}

とn重ループで、実装が煩雑で大変。

そこでビット全探索を用いた実装を行う。

for(int i=0;1>>N;i++){ //※1
      a = i;
}

上の場合例えば、$00000111$(N=8とする)に対応する7がaに代入される。

2進数にしたときの値が1の桁の数

例. 155を2進法で表したとき1を何個含むか?
ただし2進数の桁数はNとする。

int i = 155;
int cnt = 0; //カウント数
for(int j = 0; j<=N-1; j++){
       if(i&(1<<j)==1) cnt++; //※1,2
}

※1 1<<nとは1をnビット左シフトした結果。例えば1<<3は 1000(2)。
※2 i&nとはi(10)とn(10)の論理和をとる。例えば5&(1<<2) = 5&4 (10) = 101&100 (2) = 100(2) = 4

bit全探索における計算量の見積もり　”2のべき乗と10のべき乗”

Nビットについてbit全探索を行うと計算量は$2^{N}$かかるが、その値がどのくらいになるかの目安を知りたい。

$10^{3} \fallingdotseq 1024 = 2^{10} $
という関係があります。また10進数のオーダーに対しては
$O(10^6)～O(10^8)$あたりでおよそ1秒の計算時間がかかります
ただしこの時間は使用する言語やプロセッサなどにより変わります。

つまり概算として
$[2^{20},2^{26} ]= [1048576, 134217728] \fallingdotseq [10^6 ,10^8] (step) = 1(s)$
となります。