C++の練習を兼ねて, AtCoder Grand Contest 035 の 問題A (XOR Circle) ~ 問題B (Even Degrees) を解いてみた.
■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題B は, 実装に苦労したものの, グラフに対する理解を深めることが出来た気がするので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 035 解説 を ご覧下さい.
■C++版プログラム(問題A/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 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/agc035/editorial.pdf #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 #define a first #define b second int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; rep(i, N){ int a; scanf("%d", &a); m[a]++; } // 2. 判定. // 2-1. すべての帽子に書かれた数字が, 0. if(m.size() == 1 && m.count(0)){ puts("Yes"); return 0; } // 2-2. x が 書かれた帽子が, 2 * N / 3 枚, 0 が 書かれた帽子が, 1 * N / 3 枚. if(m.size() == 2 && N % 3 == 0){ vector<int> v; for(auto &p : m) v.pb(p.a); if(v[0] == 0 && m[v[0]] == N / 3){ puts("Yes"); return 0; } if(v[1] == 0 && m[v[1]] == N / 3){ puts("Yes"); return 0; } } // 2-3. x ^ y ^ z = 0 の 書かれた帽子が, 1 * N / 3 枚ずつ. if(m.size() == 3 && N % 3 == 0){ int xyz = 0; vector<int> v; for(auto &p : m) v.pb(p.a), xyz ^= p.a; if(xyz == 0 && m[v[0]] == N / 3 && m[v[1]] == N / 3 && m[v[2]] == N / 3){ puts("Yes"); return 0; } } // 2-4. それ以外. puts("No"); 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 |
[入力例] 3 1 2 3 [出力例] Yes ※AtCoderのテストケースより [入力例] 4 1 2 4 8 [出力例] No ※AtCoderのテストケースより [入力例] 2 0 0 [出力例] Yes [入力例] 6 2 2 0 0 2 2 [出力例] Yes [入力例] 9 2 5 7 2 5 7 2 5 7 [出力例] Yes |
■C++版プログラム(問題B/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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
// 解き直し. // https://img.atcoder.jp/agc035/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; using P = pair<int, int>; #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 oDegree[101010], p[101010]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); set<P> gEdges; vvi G(N); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); // 辺を保存. gEdges.insert({a, b}); gEdges.insert({b, a}); } // 2. 辺数が奇数の場合. if(gEdges.size() % 4 != 0){ puts("-1"); return 0; } // 3. 適当な根付き全域木. vvi sTree(N); set<P> stEdges; // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* d){ // 3-1. 空のキュー. queue<int> q; // 3-2. 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // 3-3. キューから取り出す. int u = q.front(); q.pop(); // 3-4. 取り出した要素を処理. for(auto &v : G[u]){ // 3-5. 訪問済であれば, 処理をスキップ. if(d[v]) continue; if(!d[v] && v != s){ d[v] = d[u] + 1; q.push(v); // グラフに反映. sTree[u].pb(v); sTree[v].pb(u); // 辺を保存. stEdges.insert({u, v}); stEdges.insert({v, u}); // 親頂点を保存. p[v] = u; } } } return; }; int d[N]; rep(i, N) d[i] = 0; bfs(G, 0, d); // 4. 根 から 遠い順 に並び替え. priority_queue<P> pq; rep(i, N) pq.push({d[i], i}); // 5. 根付き全域木に含まれない辺について向きを付ける. set<P> ans; for(auto &e : gEdges){ if(!stEdges.count(e)){ if(!ans.count({e.a, e.b}) && !ans.count({e.b, e.a})){ // 辺を保存. ans.insert(e); // 出次数を更新. oDegree[e.a]++; } } } // 6. ボトムアップで確定させていく. while(!pq.empty()){ // 6-1. キューから取り出す. P cur = pq.top(); pq.pop(); // 6-2. 根に到達したら終了. int u = cur.b; if(u == 0) break; // 6-3. 子 -> 親. if(oDegree[u] & 1){ // 辺を保存. ans.insert({u, p[u]}); // 出次数を更新. oDegree[u]++; // 次へ. continue; } // 6-4. 親 -> 子. if(!(oDegree[u] & 1)){ // 辺を保存. ans.insert({p[u], u}); // 出次数を更新. oDegree[p[u]]++; // 次へ. continue; } } // 7. チェック. int odd = 0; rep(i, N) if(oDegree[i] & 1) odd++; assert(odd == 0); // 8. 出力. for(auto &p: ans) printf("%d %d\n", p.a + 1, p.b + 1); 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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
[入力例] 4 4 1 2 2 3 3 4 4 1 [出力例] 1 2 1 4 3 2 3 4 ※AtCoderテストケースより [入力例] 5 5 1 2 2 3 3 4 2 5 4 5 [出力例] -1 ※AtCoderテストケースより [入力例] 17 20 1 2 1 6 1 9 6 7 6 5 7 5 5 4 3 5 4 13 4 14 13 14 15 4 10 9 8 9 10 11 10 12 11 12 17 12 11 16 11 17 [出力例] 1 2 1 9 4 14 4 15 5 3 5 4 5 6 5 7 6 1 6 7 9 8 9 10 11 10 11 12 11 16 11 17 12 10 12 17 13 4 13 14 [入力例] 21 26 1 2 1 7 1 9 2 4 2 3 3 5 3 6 3 14 5 6 6 20 6 21 7 8 8 14 8 15 8 16 8 9 9 11 11 16 11 10 11 12 11 13 12 13 10 17 10 18 10 19 17 18 [出力例] 1 2 1 9 2 3 2 4 3 6 3 14 5 3 5 6 6 20 6 21 7 1 7 8 8 9 8 14 8 15 8 16 10 18 10 19 11 9 11 10 11 13 11 16 12 11 12 13 17 10 17 18 |
■参照サイト
AtCoder Grand Contest 035