C++の練習を兼ねて, AtCoder Beginner Contest 191 の 問題C (Digital Graffiti), 問題E (Come Back Quickly) ～ 問題F (GCD or MIN) を解いてみた.
■感想.
1. 問題C, 問題E, 問題Fは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
※ 問題D は, よくわからなかったので, スキップ(汗)
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 191 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc191/editorial/612 // 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--) int board[22][22]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, H){ char c[22]; scanf("%s", c); rep(j, W) if(c[j] == '#') board[i][j] = 1; } // 2. 頂点を探索(周囲四マスを調べる). int ans = 0; rep(i, H - 1){ rep(j, W - 1){ int count = 0; count += board[i][j]; count += board[i + 1][j]; count += board[i][j + 1]; count += board[i + 1][j + 1]; if(count == 1 || count == 3) ans++; } } // 3. 出力. printf("%d\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 |
[入力例] 5 5 ..... .###. .###. .###. ..... [出力例] 4 ※AtCoderテストケースより [入力例] 7 7 ....... ..###.. .#####. .#####. .#####. ..###.. ....... [出力例] 12 |
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/abc191/editorial/610 // 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 pb push_back const LL INF = 202020202020202020; struct edge{ int n; // 次の頂点. LL c; // 移動時間. bool operator < (const edge &E) const{ return c > E.c; } }; LL d[2020][2020]; // i -> j の 移動時間. LL ds[2020]; // i -> i の 移動時間. LL ans[2020]; // 出力用. vector<edge> G[2020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) rep(j, N) d[i][j] = INF; rep(i, N) ds[i] = INF; rep(i, M){ int a, b; LL c; scanf("%d %d %lld", &a, &b, &c); a--, b--; edge e; e.n = b; e.c = c; G[a].pb(e); // a -> b. if(a == b) ds[a] = min(ds[a], c); // a -> a. (random_10.txt の WA回避？) } // 2. ダイクストラ法. // https://ja.wikipedia.org/wiki/ダイクストラ法 auto dijkstra = [&](int s){ // 1. 初期化. priority_queue<edge> pq; // 2. 始点設定. d[s][s] = 0; pq.push({s, 0LL}); // 3. キュー pq が 空になるまで, 探索. while(!pq.empty()){ // 4. 探索を継続するために, 頂点を取得. edge e = pq.top(); pq.pop(); int cn = e.n; LL cc = e.c; // 4. 各隣接する頂点について, 距離を確認し, 移動時間を更新. for(auto &g : G[cn]){ int nn = g.n; LL nc = cc + g.c; // 5. 移動時間更新. if(d[s][nn] > nc) d[s][nn] = nc, pq.push({nn, nc}); } } return; }; // 3. 各頂点に対して, 最短経路を求める. rep(i, N) dijkstra(i); // 4. 出力用の情報を作成. rep(i, N){ ans[i] = ds[i]; rep(j, N) if(i != j) ans[i] = min(ans[i], d[i][j] + d[j][i]); } rep(i, N) if(ans[i] >= INF) ans[i] = -1; // 5. 出力. rep(i, N) printf("%lld\n", ans[i]); 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 128 129 130 131 132 133 134 135 136 |
[入力例] 4 4 1 2 5 2 3 10 3 1 15 4 3 20 [出力例] 30 30 30 -1 ※AtCoderテストケースより [入力例] 4 6 1 2 5 1 3 10 2 4 5 3 4 10 4 1 10 1 1 10 [出力例] 10 20 30 20 ※AtCoderテストケースより [入力例] 4 7 1 2 10 2 3 30 1 4 15 3 4 25 3 4 20 4 3 20 4 3 30 [出力例] -1 -1 40 40 ※AtCoderテストケースより [入力例] 10 20 4 4 530 1 6 537 3 1 2004 6 3 420 7 8 1766 7 6 1114 2 10 751 1 10 466 2 2 358 3 6 1263 4 2 584 9 7 1252 8 1 1122 7 7 210 5 2 1285 3 10 536 8 8 18 8 5 405 4 8 1078 7 5 695 [出力例] 2961 358 1683 530 -1 1683 210 18 -1 -1 [入力例] 15 35 4 11 15 15 6 19 12 4 9 14 5 6 4 7 7 1 1 11 8 9 20 7 3 20 15 4 4 15 4 20 1 5 12 14 3 12 1 1 7 6 15 7 4 8 7 11 14 10 2 8 3 5 10 5 11 12 14 15 6 20 8 13 12 5 11 6 2 10 19 8 15 5 2 8 16 13 1 10 9 3 16 5 2 10 11 3 10 6 11 2 6 5 20 8 1 7 3 11 1 3 8 6 2 4 10 [出力例] 7 32 11 16 22 26 42 16 42 -1 11 38 47 22 16 |
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc191/editorial/586 // 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 a first #define b second LL a[2020]; // 与えられた正の整数のすべての約数を抽出. // @param X: 約数を抽出したい正の整数. // @return ret: すべての約数(※1以上). set<LL> div(LL X){ set<LL> ret; for(LL d = 1; d * d <= X; d++){ if(!(X % d)){ ret.insert(d); if(d * d != X) ret.insert(X / d); } } return ret; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // ※解説通り. // 2. 最小値計算. LL minA = 202020202020202020; rep(i, N) minA = min(minA, a[i]); // 3. 連想配列に計算結果を保存. map<LL, LL> m; rep(i, N){ set<LL> divisors = div(a[i]); for(auto &p : divisors){ if(!m.count(p)) m[p] = a[i]; else m[p] = __gcd(m[p], a[i]); } } // 4. 条件を満たすものをカウント. int ans = 0; for(auto &p : m) if(p.a == p.b && p.a <= minA) ans++; // 5. 出力. printf("%d\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 |
[入力例] 3 6 9 12 [出力例] 2 ※AtCoderテストケースより [入力例] 4 8 2 12 6 [出力例] 1 ※AtCoderテストケースより [入力例] 7 30 28 33 49 27 37 48 [出力例] 7 ※AtCoderテストケースより [入力例] 20 109 27 40 25 61 44 18 65 11 119 122 68 14 112 118 72 26 81 71 60 [出力例] 10 [入力例] 30 10424 3725 8181 11925 2195 11525 1741 4066 9820 5680 4488 7590 395 1692 7813 2406 4939 4923 11179 1595 2809 1520 6561 4327 11551 9252 8222 8454 4639 10903 [出力例] 22 |
■参照サイト
AtCoder Beginner Contest 191