C++の練習を兼ねて, AtCoder Grand Contest 012 の 問題A (AtCoder Group Contest) ～ 問題B (Splatter Painting) を解いてみた.
■感想.
1. 問題B は, 方針が見えなかったので, 解説を参照して実装したところ, 何とか, AC版となった.
2. 問題B は, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトAGC 012 解説をご覧下さい.
■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 |
// 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--) LL a[303030]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, 3 * N) scanf("%lld", &a[i]); // 2. sort. sort(a, a + 3 * N); // 3. N組のチームの強さの和としてありうる値の最大値. LL ans = 0; repex(i, N, 3 * N, 2) ans += a[i]; // 4. 出力. 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 |
[入力例] 2 5 2 8 5 1 5 [出力例] 10 ※AtCoderテストケースより [入力例] 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 [出力例] 10000000000 ※AtCoderテストケースより [入力例] 5 731007134 666726757 1084577778 425482635 159667494 1223807980 892198095 246269500 935881669 420264692 524085657 1139597661 1055646323 530808787 212504003 [出力例] 4278254493 |
■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 |
// C++(GCC 9.2.1) // 解き直し. // https://img.atcoder.jp/agc012/editorial.pdf #include <bits/stdc++.h> using namespace std; using vvi = vector<vector<int>>; using T3 = tuple<int, 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 pb push_back const int MAX = 101010; int dp[MAX][11]; // 頂点 v から 距離 d 以内にある頂点たちの色を塗る. int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); vvi G(N); rep(i, M){ int a, b; scanf("%d %d", &a, &b); a--, b--; G[a].pb(b); G[b].pb(a); } int Q; vector<T3> q; scanf("%d", &Q); rep(i, Q){ int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; q.emplace_back(a, b, c); } // 2. 色を着色する(操作の逆順). function<void(int, int, int, int)> f = [&](int pv, int sv, int d, int c) { // 距離が負数の場合は, 終了. if(d < 0) return; // 着色済みの場合は, 終了. if(dp[sv][d]) return; // 着色する. rep(i, d + 1) if(!dp[sv][i]) dp[sv][i] = c; // 隣接する頂点を着色. for(auto &cv : G[sv]){ // 親頂点以外を見に行く. if(cv != pv) f(sv, cv, d - 1, c); } }; repr(i, Q - 1, 0){ // 操作を取得. int v = get<0>(q[i]); int d = get<1>(q[i]); int c = get<2>(q[i]); // 頂点の色を塗ってない場合. if(!dp[v][d]) f(-1, v, d, c); } // 3. 出力. rep(i, N) printf("%d\n", dp[i][0]); 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 |
[入力例] 7 7 1 2 1 3 1 4 4 5 5 6 5 7 2 3 2 6 1 1 1 2 2 [出力例] 2 2 2 2 2 1 0 ※AtCoderテストケースより [入力例] 14 10 1 4 5 7 7 11 4 10 14 7 14 3 6 14 8 11 5 13 8 3 8 8 6 2 9 7 85 6 9 3 6 7 5 10 3 1 12 9 4 9 6 6 8 2 3 [出力例] 1 0 3 1 5 5 3 3 6 1 3 4 5 3 ※AtCoderテストケースより [入力例] 23 27 1 11 1 2 3 1 2 3 12 2 12 19 4 15 4 7 6 7 6 5 5 4 13 5 5 14 14 16 14 21 21 16 16 22 21 22 22 23 23 16 21 23 8 9 9 17 17 18 10 9 20 10 10 8 7 5 5 7 15 3 77 20 2 777 9 1 2020 2 2 2020 1 3 77777 1 1 7777 [出力例] 7777 7777 7777 77 77 77 77 2020 2020 2020 7777 77777 77 77 77 7 2020 0 77777 777 7 7 7 |
■参照サイト
AtCoder Grand Contest 012