C++の練習を兼ねて, AtCoder Beginner Contest 210 の 問題E (Ring MST) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 解説にあるように, 最小全域木(Kruskal’s Algorithm) の性質を使って, 最終的に, 数式まで落とし込んでいくロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 210 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc210/editorial/2299 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; #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 all(x) x.begin(), x.end() #define a first #define b second int main(){ // 1. 入力情報. int M; LL N; scanf("%lld %d", &N, &M); vp v; rep(i, M){ LL a, c; scanf("%lld %lld", &a, &c); v.pb({c, a}); } // 2. sort. // -> 解説にある通り, 最小全域木(Kruskal's Algorithm) を ベースに考えるため必要. sort(all(v)); // 3. コストの最小値は? LL ans = 0, bef = N, cur; for(auto &p : v){ // 今回分更新. cur = __gcd(bef, p.b); // 集計. ans += p.a * (bef - cur); // 前回分更新. bef = cur; } // 4. 全域木が無い場合. if(cur > 1) ans = -1; // 5. 出力. 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 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 |
[入力例] 4 2 2 3 3 5 [出力例] 11 ※AtCoderテストケースより [入力例] 6 1 3 4 [出力例] -1 ※AtCoderテストケースより [入力例] 8 3 2 1 4 2 6 3 [出力例] -1 [入力例] 10 9 1 9 2 8 3 7 4 6 5 5 6 4 7 3 8 2 9 1 [出力例] 9 [入力例] 32 10 12 5 16 1 22 13 31 10 1 7 19 3 21 8 3 17 17 5 26 10 [出力例] 61 [入力例] 33333 22 19002 32181 25701 58593 18097 46854 383 94737 14074 64088 5079 170351 17624 152448 21230 18133 1601 73981 31329 28493 22453 10214 3365 132535 9035 127417 28030 170783 14237 68665 13917 179105 21643 104707 6672 65054 30083 196465 31715 98708 19864 154275 25748 53992 [出力例] 340453048 |
■参照サイト
AtCoder Beginner Contest 210