C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題C (ABland Yard) を解いてみた.
■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 文字列が作れるかどうかを, グラフの性質に基づいて解いていく部分が, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 027 解説 を ご覧下さい.
■C++版プログラム(問題C／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 |
// 解き直し. // https://img.atcoder.jp/agc027/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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 set<int> G[202020]; int info[202020][3]; // 第一成分: 'A' の 個数, 第二成分: 'B' の 個数, 第三成分: 'A', 'B' の 種類数. int main(){ // 1. 入力情報. int N, M; char s[202020]; scanf("%d %d %s", &N, &M, s); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].insert(b); G[b].insert(a); } // 2. 各頂点ごとに, 'A', 'B' の 個数 を 保存. rep(i, N){ // 2-1. 頂点 i の隣接頂点を確認して, 'A', 'B' の個数 を カウント. for(auto &v : G[i]){ if(s[v] == 'A') info[i][0]++; if(s[v] == 'B') info[i][1]++; } // 2-2. 'A', 'B' が, 1個以上ある場合に, 種類数 を インクリメント. if(info[i][0]) info[i][2]++; if(info[i][1]) info[i][2]++; } // 3. 頂点(種類数 1) を 保存. queue<int> q; rep(i, N) if(info[i][2] == 1) q.push(i); // 4. グラフから, 種類数が, 1以下 の 頂点 を取り除いていく. while(!q.empty()){ // 4-1. 頂点 u に 関する情報を取得. int u = q.front(); q.pop(); int lu = s[u] - 'A'; // 4-2. 種類数 を 確認. if(!info[u][2]) continue; // 4-3. 取り出した要素を処理. for(auto &v : G[u]){ // 4-4. 種類数 を 確認. if(!info[v][2]) continue; // 4-5. u, v が 等しい場合. if(u == v){ info[u][lu]--; continue; } // 4-6. G[v] から, u を 取り除く. int lv = s[v] - 'A'; G[v].erase(u); info[u][lv]--; info[v][lu]--; // 4-7. 種類数が, 1 の場合に, 追加. if((info[v][0] && !info[v][1]) || (!info[v][0] && info[v][1])) q.push(v), info[v][2] = 1; } // 4-8. G[u] を 処理. assert(info[u][0] == 0); assert(info[u][1] == 0); info[u][2] = 0; G[u].clear(); } // 5. グラフが残存しているかチェック. int ans = 0; rep(i, N) ans += G[i].size(); // 6. 出力. printf("%s\n", (ans == 0) ? "No" : "Yes"); 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 108 109 110 111 |
[入力例] 2 3 AB 1 1 1 2 2 2 [出力例] Yes ※AtCoderのテストケースより [入力例] 4 3 ABAB 1 2 2 3 3 1 [出力例] No ※AtCoderのテストケースより [入力例] 13 23 ABAAAABBBBAAB 7 1 10 6 1 11 2 10 2 8 2 11 11 12 8 3 7 12 11 2 13 13 11 9 4 1 9 7 9 6 8 13 8 6 4 10 8 7 4 3 2 1 8 12 6 9 [出力例] Yes ※AtCoderのテストケースより [入力例] 13 17 BBABBBAABABBA 7 1 7 9 11 12 3 9 11 9 2 1 11 5 12 11 10 8 1 11 1 8 7 7 9 10 8 8 8 12 6 2 13 11 [出力例] No ※AtCoderのテストケースより [入力例] 5 8 ABABA 1 2 1 3 1 1 1 5 2 3 4 5 3 4 2 4 [出力例] Yes [入力例] 7 12 AABBABA 1 2 2 3 3 4 4 5 5 6 6 7 7 1 1 7 2 3 1 5 6 4 3 6 [出力例] No |
■参照サイト
AtCoder Grand Contest 027