C++の練習を兼ねて, AtCoder Regular Contest 164 の 問題A (Ternary Decomposition) ~ 問題C (Reversible Card Game) を解いてみた.
■感想.
1. 問題A ~ C は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 各問とも, 解説のロジックで解ける点が, 興味深く思った.
3. Union-Find木 の 復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 164 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc164/editorial/6635 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 T; scanf("%d", &T); // 2. 3 の 冪乗. vl pow3; pow3.pb(1); while(pow3.back() < 1e18) pow3.pb(pow3.back() * 3); // for(auto &x : pow3) printf("%lld\n", x); // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. LL N, K; scanf("%lld %lld", &N, &K); // 3-2. L を 計算. LL L = 0, cur = N; repr(i, pow3.size() - 1, 0){ L += cur / pow3[i]; cur %= pow3[i]; } // 3-3. 判定. bool ok = true; if((N - K) & 1) ok = false; if(K < L) ok = false; // 3-4. 出力. printf("%s\n", ok ? "Yes" : "No"); } 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 |
[入力例] 4 5 3 17 2 163 79 1000000000000000000 1000000000000000000 [出力例] Yes No Yes Yes ※AtCoderのテストケースより [入力例] 20 7426863 17 10150951 5639271 9778798 15 5512894 2095080 10651982 5864016 11070422 3178139 5512162 9 2323820 550448 7350312 3507402 7220916 3729451 10744158 4787482 7857992 6880983 10461811 2006563 4086887 330608 5970335 1062393 6005971 2674798 12290876 9857165 11758323 9377833 4830691 10 11705751 1232255 [出力例] Yes Yes No Yes Yes No No Yes Yes No Yes No Yes No Yes No No Yes No Yes [入力例] 30 2023 1 2023 2 2023 3 2023 4 2023 5 2023 6 2023 7 2023 8 2023 9 2023 10 2023 11 2023 12 2023 13 2023 14 2023 15 2023 16 2023 17 2023 18 2023 19 2023 20 2023 21 2023 22 2023 23 2023 24 2023 25 2023 26 2023 27 2023 28 2023 29 2023 30 [出力例] No No No No No No No No No No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No Yes No |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc164/editorial/6633 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vi = vector<int>; 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 a first #define b second // 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, M; scanf("%d %d", &N, &M); vp e(M); rep(i, M){ scanf("%d %d", &e[i].a, &e[i].b); --e[i].a; --e[i].b; } int c[N]; rep(i, N) scanf("%d", &c[i]); // 2. 異なる色の頂点間のみ辺を結ぶ. UnionFind uf(N + 2); rep(i, M) if(c[e[i].a] != c[e[i].b]) uf.unite(e[i].a, e[i].b); // 3. 同じ連結成分内に, 同じ色の頂点間の辺が存在するか? bool ok = false; rep(i, M){ if(c[e[i].a] == c[e[i].b]){ if(uf.same(e[i].a, e[i].b)){ ok = true; break; } } } // 4. 出力. printf("%s\n", ok ? "Yes" : "No"); 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 |
[入力例] 4 4 1 2 2 3 3 4 4 2 0 1 0 1 [出力例] Yes ※AtCoderのテストケースより [入力例] 5 6 1 2 2 3 3 4 4 5 1 4 2 5 0 1 0 1 0 [出力例] No ※AtCoderのテストケースより [入力例] 10 12 1 2 1 4 4 2 3 2 3 4 6 4 6 5 7 6 7 5 10 7 8 5 9 8 1 0 1 0 0 0 0 0 1 1 [出力例] Yes [入力例] 20 30 1 2 3 2 4 2 1 6 4 3 3 17 17 5 5 3 5 4 7 4 7 6 14 6 16 14 16 15 15 8 8 6 8 7 9 7 9 8 10 5 10 9 18 9 19 18 12 10 12 18 11 10 13 11 13 12 12 20 20 19 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 [出力例] Yes |
■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 41 42 43 44 45 46 47 48 49 50 51 52 |
// 解き直し. // https://atcoder.jp/contests/arc164/editorial/6632 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<int, int>; 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 a first #define b second const LL INF = 202020202020202020; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp v(N); rep(i, N) scanf("%d %d", &v[i].a, &v[i].b); // 2. A[i] > B[i] の 枚数は? int c = 0; rep(i, N) c += (v[i].a > v[i].b); // 3. 合計. LL ans = 0; rep(i, N) ans += max(v[i].a, v[i].b); // 4. c が 奇数. if(c & 1){ LL a = 0, b = 0, d = INF; rep(i, N){ if(d > abs(v[i].a - v[i].b)){ d = abs(v[i].a - v[i].b); a = v[i].a; b = v[i].b; } } if(a < b) swap(a, b); ans -= a; ans += b; } // 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 |
[入力例] 3 6 4 2 1 5 3 [出力例] 12 ※AtCoderのテストケースより [入力例] 5 166971716 552987438 219878198 619875818 918378176 518975015 610749017 285601372 701849287 307601390 [出力例] 3078692091 ※AtCoderのテストケースより [入力例] 7 52 59 135 122 139 30 6 65 14 117 25 120 149 2 [出力例] 777 [入力例] 15 4862323 6596410 10091334 9475430 8026286 3722785 9697285 9634926 6126041 6139508 7726831 7922969 6938205 10026399 7559913 8125061 944108 555259 10266617 3004763 3333758 10086811 4775931 8535374 10116049 7211752 8485351 6963035 417896 8410694 [出力例] 123456789 |