C++の練習を兼ねて, AtCoder Grand Contest 049 の 問題A (Erasing Vertices) ～ 問題B (Flip Digits) を解いてみた.
■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 問題A で, 幅優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題A, B のいずれも, 解説のロジックが, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Grand Contest 049 解説 の 各リンク を ご覧下さい.
■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 63 64 65 66 67 |
// 解き直し. // https://atcoder.jp/contests/agc049/editorial/281 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 int main(){ // 1. 入力情報. int N; scanf("%d", &N); vvi G(N); rep(i, N){ char c[101]; scanf("%s", c); rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺. } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vvi &G, int s, int* d){ // 空のキュー. queue<int> q; // 距離ゼロを設定. d[s] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 隣接頂点をチェック. for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v); } }; // 3. S[v] の 計算(解説通り). vvi S(N); rep(i, N){ // 頂点 i から, 到達可能な頂点は？ int d[N]; rep(j, N) d[j] = -1; bfs(G, i, d); // S[v] に 保存. rep(v, N) if(d[v] != -1) S[v].pb(i); } // 4. 集計. double ans = 0.0; rep(v, N) ans += 1.0 / (double)S[v].size(); // 5. 出力. printf("%.12lf\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 |
[入力例] 3 010 001 010 [出力例] 1.66666666666666666667 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 1.666666666667 [入力例] 3 000 000 000 [出力例] 3.00000000000000000000 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 3.000000000000 [入力例] 3 011 101 110 [出力例] 1.00000000000000000000 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 1.000000000000 [入力例] 4 0100 0010 0001 0100 [出力例] 1.750000000000 [入力例] 5 01001 00100 00010 01000 00000 [出力例] 2.250000000000 [入力例] 10 0100000100 0010010000 0001000001 0000100000 0000000000 0000001000 0000000000 0000000010 0000000000 0000000000 [出力例] 3.950000000000 [入力例] 15 010000000010000 000000000000000 000100000000100 000010000000010 000000000100001 000000000000100 000000000010001 000000000000000 000000010000000 000001000000000 000010000000000 000100000000000 000000000000010 010000000000000 110000000000000 [出力例] 5.795609945610 |
■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 |
// 解き直し. // https://atcoder.jp/contests/agc049/editorial/330 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) int sXorCum[505050], tXorCum[505050], cur[2]; int main(){ // 1. 入力情報. int N; char s[505050], t[505050]; scanf("%d %s %s", &N, s, t); // 2. 累積XOR. rep(i, N){ sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1'); tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1'); } // 3. 操作(解説通り). int k = -1, jMax = -1; LL ans = 0; bool ok = true; repx(i, 1, N + 1){ // すでに, tXorCum と sXorCum が 一致しているときは, Skip. if(cur[tXorCum[i]] >= i) continue; // 探索開始位置(今回分). k = max(jMax, i); // 探索済みにも関わらず, tXorCum と sXorCum が 一致しない場合は, NG. if(k == N + 1) ok = false; // tXorCum の i番目 と sXorCum の j番目 が 等しくなるものは？ repx(j, k, N + 1){ // 探索開始位置(次回分). jMax = max(jMax, j + 1); // 見つかった. if(tXorCum[i] == sXorCum[j]){ // 集計. ans += (j - i); // 操作履歴保存. cur[tXorCum[i]] = j; cur[!tXorCum[i]] = -1; // 次へ. break; } // 見つからなかった. if(jMax == N + 1) ok = false; } } // 4. 出力. printf("%lld\n", ok ? ans : -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 |
[入力例] 3 001 100 [出力例] 2 ※AtCoderのテストケースより [入力例] 3 001 110 [出力例] -1 ※AtCoderのテストケースより [入力例] 5 10111 01010 [出力例] 5 ※AtCoderのテストケースより [入力例] 7 0101101 1001100 [出力例] -1 [入力例] 7 0111101 1001100 [出力例] 5 [入力例] 10 1010111101 1000101100 [出力例] -1 [入力例] 10 1010111101 1100101100 [出力例] 5 [入力例] 30 001010001110011100110110111101 110001010100011100100110011000 [出力例] 18 |
■参照サイト
AtCoder Grand Contest 049