質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1668閲覧

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

kei0105

総合スコア7

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2020/12/11 02:32

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

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

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

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

実装コード

c++

1#include <bits/stdc++.h> 2using namespace std; 3 4int main() { 5 int n, m; cin >> n >> m; 6 vector<vector<int>> graph(12, vector<int>(12)); 7 8 for(int i = 0; i < m; i++){ //関係が存在する二次元配列にフラグ(1)を立てる 9 int x, y; cin >> x >>y; 10 x--; y--; // 配列は0スタートだから毎回デクリメント 11 graph[x][y] = 1; graph[y][x] = 1; 12 } 13 14 int ans = 1; 15 for(int mask = 0; mask < (1 << n); mask++){ 16 vector<int> as; 17 for(int i = 0; i < n; i++){ 18 if(1 & (mask >> i)) as.push_back(i); 19 } 20 21 bool ok = true; 22 for(auto i : as){ 23 for(auto j : as){ 24 if(i == j) continue; 25 if(graph[i][j] != 1) ok = false; 26 } 27 } 28 29 if(ok) ans = max(ans, (int)as.size()); 30 } 31 cout << ans << endl; 32} 33

具体的な不明部分

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; } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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

  • 1人派閥が3パターン
  • 2人派閥が3パターン
  • 3人派閥が1パターン

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

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

投稿2020/12/11 02:55

fana

総合スコア11632

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

fana

2020/12/11 02:56

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

2020/12/11 17:19

回答ありがとうございます for(int i = 0; i < n; i++){ if(1 & (mask >> i)) } ここのfor分は何の為繰り返しているのですか。ifの条件は何を示したいのでしょうか。
fana

2020/12/12 01:25 編集

それを回答しているのだが…… 例えば n=3 のとき mask の範囲は 0~7. これはつまり 3bit で表現できる値. iはmaskを右シフトするのに使ってるんだから,for文はシフト量を変えてるだけ. そのforで,maskの値を{0bit, 1bit, 2bit}シフトした際の最下位bitを調べてる. (つまり,maskの値について,どのbitが立ってるかを調べてるだけだ) 実際に紙上でやってみたらどうです? n=3 とかなら5分くらいで仕組みがわかるでしょう.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問