C++の練習を兼ねて, AtCoder Beginner Contest 282 の 問題E (Choose Two and Eat One) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 282 解説 の 各リンク を ご覧下さい.
■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 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://atcoder.jp/contests/abc282/editorial/5398 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; using vl = vector<LL>; using T3 = tuple<LL, 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 all(x) x.begin(), x.end() // Fermat's little theorem から, 大きな冪乗の計算を行う. // -> 引数 MOD は, 素数と限らないので, 逆元の計算には, 使用しない. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b, LL MOD){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } // https://github.com/atcoder/live_library/blob/master/uf.cpp // UnionFind // coding: https://youtu.be/TdR816rqc3s?t=726 // comment: https://youtu.be/TdR816rqc3s?t=6822 // -> 一部改変. struct UnionFind{ vi d; UnionFind(int n = 0): d(n, -1) {} int find(int x){ return (d[x] < 0) ? x : (d[x] = find(d[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(d[x] > d[y]) swap(x, y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y){ return find(x) == find(y); } int size(int x){ return -d[find(x)]; } }; int main(){ // 1. 入力情報. int N; LL M; scanf("%d %lld", &N, &M); vl a(N); rep(i, N) scanf("%lld", &a[i]); // 2. 辺情報. vector<T3> t; rep(u, N) repx(v, u + 1, N) t.emplace_back((mPow(a[u], a[v], M) + mPow(a[v], a[u], M)) % M, u, v); // 3. sort. // -> 最大全域木 を 構築するため, 降順で並び替える. sort(all(t)); reverse(all(t)); // 4. 最大全域木. // -> 最小全域木(Kruskal's Algorithm) の アルゴリズム を 流用. // 競プロ典型 90 問 (049 - Flip Digits 2) // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp UnionFind uf(N + 2); LL ans = 0; rep(i, t.size()){ // 4-1. グラフ情報. int u = get<1>(t[i]); int v = get<2>(t[i]); LL cost = get<0>(t[i]); // 4-2. 辺 を 追加. if(!uf.same(u, v)){ uf.unite(u, v); ans += cost; } } // 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 |
[入力例] 4 10 4 2 3 2 [出力例] 20 ※AtCoderテストケースより [入力例] 20 100 29 31 68 20 83 66 23 84 69 96 41 61 83 37 52 71 18 55 40 8 [出力例] 1733 ※AtCoderテストケースより [入力例] 5 25 7 24 17 12 3 [出力例] 60 [入力例] 20 2023 877 1532 1740 388 462 252 1299 421 841 1235 994 1761 639 868 560 632 1042 1265 314 671 [出力例] 36147 [入力例] 200 20230113 18581675 4274380 17829716 12271757 16916200 1801487 19665242 5334036 4149560 15459494 15009176 13960748 17980544 7812492 6551123 16646042 4931704 15515582 664316 13659957 13248666 16041711 1175879 6251446 1765631 11159012 4595851 19069927 16750999 15386170 15261501 17331674 13525451 2537306 9130297 6746448 5611532 19698071 3756218 16877032 13992225 2580209 18423027 12538584 1432012 8446157 2422875 15411158 15178100 16045055 10960697 5312125 18010947 16866996 19069532 5673025 13311148 9928007 10637002 3927509 10616580 7472782 10241197 5355881 4791590 1741882 13050504 16134873 794851 10155052 19085692 15259444 18497994 16237086 12574864 904170 17500959 17751459 16908642 10401729 19386260 15502160 11247117 6231333 13477170 725403 11788249 5343633 9634343 19517803 18302876 6091777 16251194 6956039 11047990 13970323 13658944 7773722 5159731 11256668 1910547 13838026 16677238 1059524 15208750 20132229 19088533 11249240 16513896 4838707 5282521 3498958 6440002 12747410 11606399 5363413 16472850 6482823 4871440 13118149 18764972 11846496 14760037 16155126 13472131 5684766 1097515 9962678 9855707 11379308 17577264 2261296 7262536 9544603 17909797 4991889 19637396 9794908 8014022 17119197 15241735 9608467 20002119 13530795 8052363 14067583 3304908 8033144 9290093 10359397 5951141 15090209 1115963 16137160 12718867 18909523 9630118 10792540 6057036 10400061 897345 14155403 12196582 17996942 8863261 18423454 2684276 13130763 8531789 6656673 2288890 5587375 8044163 4316572 3282614 13257153 19098256 16295289 10977860 9649381 13672792 10120501 7639862 5445919 19413562 1048660 19782177 16185142 18790452 3909213 12116149 18583901 10285888 996135 7594577 13815619 9946295 13640951 13048670 14564381 [出力例] 3998446571 [入力例] 500 23 8 6 9 11 22 16 4 19 18 2 5 20 22 20 19 7 3 4 14 2 16 16 20 17 7 15 22 15 5 12 1 6 4 14 16 14 12 3 18 19 19 12 11 2 10 8 4 4 8 13 2 18 8 6 12 19 16 15 22 19 13 8 8 14 14 8 16 2 22 12 11 5 12 11 6 7 20 22 18 4 5 4 3 19 9 4 6 14 13 8 4 11 18 5 11 19 13 17 10 19 18 18 6 21 14 14 22 18 7 10 15 13 2 15 12 16 21 18 9 2 17 21 10 14 2 12 18 11 5 13 16 18 13 8 6 1 4 11 11 8 16 18 4 9 10 10 16 17 13 5 20 22 20 17 22 10 5 4 19 14 1 10 20 1 14 8 11 6 15 3 15 6 3 3 9 20 2 1 14 18 21 17 15 2 18 3 13 3 13 12 14 11 1 14 16 16 3 22 21 11 7 4 4 19 20 11 16 12 20 3 2 12 8 1 7 17 6 4 13 17 13 11 18 12 10 11 7 3 18 15 4 17 12 21 2 14 8 12 19 16 11 21 21 11 14 16 4 17 11 10 17 12 9 10 18 21 1 3 19 12 12 17 12 9 19 2 4 1 5 13 16 14 3 21 9 21 14 4 14 9 9 6 22 22 11 8 4 21 20 19 19 15 7 19 21 10 4 19 21 6 21 1 17 2 14 1 8 3 9 8 5 2 17 14 13 18 7 4 15 21 2 16 21 2 17 14 12 13 12 22 21 9 12 9 2 20 8 6 8 22 10 3 5 5 6 17 14 4 12 14 10 14 14 19 12 14 10 11 18 16 22 18 13 20 18 7 12 21 22 5 16 11 8 6 12 22 22 7 9 7 16 22 11 22 4 9 18 13 6 4 22 4 3 6 18 9 21 2 4 20 12 18 9 6 21 13 17 14 22 18 18 19 10 14 16 9 14 12 3 4 13 3 22 6 9 3 7 9 4 18 10 5 4 22 15 15 16 6 19 21 6 13 8 21 5 12 19 3 8 14 4 4 15 17 5 14 3 10 20 1 21 12 16 2 10 2 5 16 6 12 17 20 17 1 5 3 20 9 8 15 11 8 9 13 9 10 21 7 21 13 10 3 15 7 20 10 9 22 6 19 [出力例] 10221 |
■参照サイト
HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)