C++の練習を兼ねて, AtCoder Grand Contest 039 の 問題A (Connection and Disconnection) ～ 問題B (Graph Partition) を解いてみた.
■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 二部グラフの性質を確認出来たので, 非常に良かったと思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 039 解説 を ご覧下さい.
■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://img.atcoder.jp/agc039/editorial.pdf // 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--) #define pob pop_back #define pub push_back int main(){ // 1. 入力情報. char c[111]; LL K; scanf("%s %lld", c, &K); string S(c); S.pub('#'); // 2. S を 連続する文字列 に 分割. vector<string> v; char bef, cur; string s = ""; rep(i, S.size()){ // 2-1. 今回分更新. cur = S[i]; // 2-2. 比較. if(i){ if(bef != cur){ v.pub(s); s = ""; } } s.pub(cur); // 2-3. 前回分更新. bef = cur; } S.pob(); // 3. 必要な操作の回数の最小値は？ // 3-1. 全文字同じ場合. LL ans = 0; if(v.size() == 1) ans = (LL)S.size() * K / 2; // 3-2. S の先頭・末尾の文字が異なる場合. if(v.size() > 1 && S.front() != S.back()){ for(auto &p : v) ans += (LL)(p.size() / 2); ans *= K; } // 3-3. S の先頭・末尾の文字が同じ場合. if(v.size() > 1 && S.front() == S.back()){ for(auto &p : v) ans += (LL)(p.size() / 2); ans *= K; LL a = v.front().size(); LL b = v.back().size(); ans -= (K - 1) * (a / 2 + b / 2 - (a + b) / 2); } 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 |
[入力例] issii 2 [出力例] 4 ※AtCoderテストケースより [入力例] qq 81 [出力例] 81 ※AtCoderテストケースより [入力例] cooooooooonteeeeeeeeeest 999993333 [出力例] 8999939997 ※AtCoderテストケースより [入力例] abbccc 3 [出力例] 6 [入力例] coonnneeeecccccttttttiiiiiiioooooooonnnnnnnnn 7 [出力例] 140 |
■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 |
// 解き直し. // https://img.atcoder.jp/agc039/editorial.pdf // 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 S[222][222]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ char c[222]; scanf("%s", c); rep(j, N) S[i][j] = c[j] - '0'; } // 2. グラフ作成. vvi G(N); rep(i, N) rep(j, N) if(S[i][j]) G[i].pb(j); // 3. 頂点1 からの距離を計算. // 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 &e : G[u]){ // 3-5. 訪問済であれば, 処理をスキップ. if(d[e]) continue; if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e); } } return; }; int d[N]; rep(i, N) d[i] = 0; bfs(G, 0, d); // rep(i, N) printf("%d ", d[i]); // puts(""); // 4. 二部グラフか？ // 4-1. 最短距離の偶奇で, 頂点を分類. set<int> st1, st2; rep(i, N){ // 奇数の場合. if(d[i] & 1) st1.insert(i); // 偶数の場合. else st2.insert(i); } // 4-2. 分類した頂点集合内に辺が存在するかチェック. bool bipartite = true; for(auto &p : st1) for(auto &q : st1) if(S[p][q]) bipartite = false; for(auto &p : st2) for(auto &q : st2) if(S[p][q]) bipartite = false; // 4-3. 二部グラフでない場合. if(!bipartite){ puts("-1"); return 0; } // 5. グラフの直径を計算. // -> 解説上 の Warshall–Floyd法 の 適用方法が, よく分からなかったので, // bfs を すべての頂点に対して使う方針で, 実装. int ans = 0; rep(i, N){ // 5-1. 各頂点を開始始点として, 最短距離を計算. rep(i, N) d[i] = 0; bfs(G, i, d); // 5-2. 頂点i からの 最長距離を取得. int r = 0; rep(i, N) r = max(r, d[i]); // 5-3. 最大値を更新. ans = max(ans, r); } // 6. 出力. printf("%d\n", 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 |
[入力例] 2 01 10 [出力例] 2 ※AtCoderテストケースより [入力例] 3 011 101 110 [出力例] -1 ※AtCoderテストケースより [入力例] 6 010110 101001 010100 101000 100000 010000 [出力例] 4 ※AtCoderテストケースより [入力例] 7 0110000 1000100 1001100 0010001 0110010 0000100 0001000 [出力例] 5 [入力例] 11 01110000000 10001001100 10001000000 10000000000 01100110000 00001000100 00001000000 01000000011 01000100000 00000001000 00000001000 [出力例] 5 |
■参照サイト
AtCoder Grand Contest 039