C++の練習を兼ねて, AtCoder Beginner Contest 199 の 問題D (RGB Coloring 2) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 199 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題D/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 |
// 解き直し. // https://atcoder.jp/contests/abc199/editorial/1163 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, int>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi G(N); vp E; rep(i, M){ int a, b; scanf("%d %d", &a, &b); --a, --b; G[a].pb(b); G[b].pb(a); E.pb({a, b}); } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* c, int* d, int l){ // 空のキュー. queue<int> q; // 連結成分番号 を 設定. c[s] = l; // 距離 を 設定. d[s] = 1; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 取り出した要素を処理. for(auto &e : G[u]){ if(!c[e] && e != s){ c[e] = l; d[e] = d[u] ^ 1; q.push(e); } } } }; // 3. 数え上げ. LL ans = 0; rep(i, 1 << N){ // 3-1. 赤頂点設定. int red[N]; rep(j, N) red[j] = ((1 << j) & i) ? 1 : 0; // 3-2. 赤頂点 に 矛盾がないか? bool ok = true; for(auto &p : E){ // 赤頂点同士 を 結ぶ辺 が 見つかったら, NG. if(red[p.a] && red[p.b]){ ok = false; break; } } // 3-3. Skip. if(!ok) continue; // 3-4. グラフ構築. vvi H(N); for(auto &p : E){ // 赤頂点Skip. if(red[p.a] || red[p.b]) continue; // 辺追加. H[p.a].pb(p.b); H[p.b].pb(p.a); } // 3-5. 各連結成分に分解, かつ, 距離(0 or 1) を 保存. int c[N], d[N], idx = 0; rep(j, N) c[j] = d[j] = 0; rep(j, N) if(!c[j] && !red[j]) bfs(H, j, c, d, ++idx); // 3-6. 緑頂点, 青頂点 に 矛盾がないか? for(auto &p : E){ // 赤頂点Skip. if(red[p.a] || red[p.b]) continue; // 緑頂点同士, 青頂点同士 を 結ぶ辺 が 見つかったら, NG. if(!(d[p.a] ^ d[p.b])){ ok = false; break; } } // 3-7. 加算. if(ok) ans += (1LL << idx); } // 4. 出力. printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
[入力例] 3 3 1 2 2 3 3 1 [出力例] 6 ※AtCoderテストケースより [入力例] 3 0 [出力例] 27 ※AtCoderテストケースより [入力例] 4 6 1 2 2 3 3 4 2 4 1 3 1 4 [出力例] 0 ※AtCoderテストケースより [入力例] 20 0 [出力例] 3486784401 ※AtCoderテストケースより [入力例] 10 12 1 2 1 3 2 3 2 4 3 4 4 5 5 6 5 7 9 6 10 7 8 6 8 7 [出力例] 288 [入力例] 10 5 1 2 2 3 3 4 4 5 5 1 [出力例] 7290 [入力例] 15 15 1 2 2 3 3 4 4 5 5 1 3 6 6 7 7 8 8 9 9 10 10 6 11 12 13 14 14 15 15 13 [出力例] 21600 [入力例] 16 15 1 2 3 2 4 3 5 6 6 7 7 5 8 9 9 10 11 10 11 8 12 13 13 14 14 15 15 16 16 12 [出力例] 77760 |