AtCoder ABC 002 D - 派閥をbit全探索で理解したい

Question

AtCoder ABC 002 D - 派閥 をbit全探索で理解したい

AtCoder Beginner Contest 002 - 派閥　にて、解法がわからなかったので解答の例を調べるもよく分からなかったため質問します。

問題：https://atcoder.jp/contests/abc002/tasks/abc002_4

以下、ネットの解答例を参考に作成したのですが、配列asが何なのか、as宣言後のforが何を示したいのか、asの要素数で二重ループをなぜ行なっているのでしょうか。

実装コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, m; cin >> n >> m;
  vector<vector<int>> graph(12, vector<int>(12));

  for(int i = 0; i < m; i++){ //関係が存在する二次元配列にフラグ（1）を立てる
    int x, y; cin >> x >>y;
    x--; y--; // 配列は0スタートだから毎回デクリメント
    graph[x][y] = 1; graph[y][x] = 1;
  }

  int ans = 1;
  for(int mask = 0; mask < (1 << n); mask++){
    vector<int> as;
    for(int i = 0; i < n; i++){
      if(1 & (mask >> i)) as.push_back(i);
    }

    bool ok = true;
    for(auto i : as){
      for(auto j : as){
        if(i == j) continue;
        if(graph[i][j] != 1) ok = false;
      }
    }

    if(ok) ans = max(ans, (int)as.size());
  }
  cout << ans << endl;
}

具体的な不明部分

    for(int i = 0; i < n; i++){
      if(1 & (mask >> i)) as.push_back(i);
    }

    bool ok = true;
    for(auto i : as){
      for(auto j : as){
        if(i == j) continue;
        if(graph[i][j] != 1) ok = false;
      }
    }

Answer 1

for(int mask = 0; mask < (1 << n); mask++)のループにて，考えられる派閥パターンを全て調べているだけに見えます．

例えば n=3 のとき，考えられる派閥パターンは，7パターン：

• １人派閥が3パターン
• ２人派閥が3パターン
• ３人派閥が1パターン

（コードでは加えて「0人派閥」も処理していると見えるので全8パターンを処理している形になるが）

で，asには各パターンにおける構成員のindexを入れているのですね．
例えば，３人派閥パターンのときは，asの要素は{0,1,2} ．
後段の二重ループは，このパターンが大丈夫かどうか（0,1,2　が互いに知り合いかどうか）のチェックです．

Comments

[fana]

実際に n=3 とか小さい値を例にして，asの中身がどうなるのかを考えてみればよいかと．

[kei0105]

回答ありがとうございます

for(int i = 0; i < n; i++){
if(1 & (mask >> i))
}

ここのfor分は何の為繰り返しているのですか。ifの条件は何を示したいのでしょうか。

[fana]

それを回答しているのだが……

例えば n=3 のとき mask の範囲は 0～7．
これはつまり 3bit で表現できる値．
iはmaskを右シフトするのに使ってるんだから，for文はシフト量を変えてるだけ．
そのforで，maskの値を｛0bit, 1bit, 2bit｝シフトした際の最下位bitを調べてる．
（つまり，maskの値について，どのbitが立ってるかを調べてるだけだ）

実際に紙上でやってみたらどうです？
n=3 とかなら5分くらいで仕組みがわかるでしょう．