初めてのビット操作を使った全探索

問題 (AtCoder ABC002 D)

abc002.contest.atcoder.jp

ソースコード

解説

ビット操作により全探索をする。この問題はNの数が最大でも12なので、最大でも2¹² = 4096通り。 候補に対して、その要素を含むか否かの２パターンを12要素分行う。 その際、その要素を含むか否かをビットを用いて管理する。 含む=> 1 含まない=> 0

例 N = 4の時、N桁の２進数で管理「0000」。 0001: 一つ目の要素が含まれる 0100: ３つ目の要素が含まれる 0101: １つ目と３つ目の要素が含まれる

ポイント1

要素を含むか否かを全列挙するためにビット操作

for (int i = 0; i < 1<<N; i++) {
   //....
}

このループで全てのパターンを列挙できる。 1<<Nについて

<<演算子は指定した数値の数だけ左にシフトするというもの。 つまり、N = 3 のとき、1<<Nは1<<3となり、1000となる。 この時、i < 1000 → iが111まで繰り返すことになる。(２進数だから1000の１つ前は111) これより、このループでは全てのパターンを列挙することができる。

ループ中のiの動き

0
1
10
11
100
101
110
111
1000

ポイント２

if ((1 & i >> j) == 1) { 

について これは、２進数のそれぞれの桁数を見てあげて、その要素が１であればリストに追加するという処理。

例

i = 101の時
  j = 0 (シフト無し)
  ``1 & i >> j`` → `` 1 & 101`` (1& は一桁目を見るから) → 1

  j = 1 (１つ右にシフト)
  ``1 & i >> j`` → `` 1 & 10`` (1& は一桁目を見るから) → 0

  j = 2 (２つ右にシフト)
  ``1 & i >> j`` → `` 1 & 1`` (1& は一桁目を見るから) → 1

コレによってiの中でフラグが立っている要素のみ、リストに加える事ができる。