C++の練習を兼ねて, AtCoder Beginner Contest 272 の 問題C (Max Even) ~ 問題E (Add and Mex) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題D で, 幅優先探索 の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 272 解説 の 各リンク を ご覧下さい.
■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 |
// 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 a[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); // 2. sort. sort(a, a + N); // 3. 大きな二つの奇数, 偶数. int o1 = -1, o2 = -1, e1 = -1, e2 = -1; repr(i, N - 1, 0){ // 奇数. if(a[i] & 1){ if(o1 == -1){ o1 = a[i]; continue; } if(o1 != -1 && o2 == -1) o2 = a[i]; } // 偶数. if(!(a[i] & 1)){ if(e1 == -1){ e1 = a[i]; continue; } if(e1 != -1 && e2 == -1) e2 = a[i]; } } // 4. 最大値は? int ans = -1; if(o1 != -1 && o2 != -1) ans = max(ans, o1 + o2); if(e1 != -1 && e2 != -1) ans = max(ans, e1 + e2); // 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 |
[入力例] 3 2 3 4 [出力例] 6 ※AtCoderテストケースより [入力例] 2 1 0 [出力例] -1 ※AtCoderテストケースより [入力例] 10 9 3 0 10 8 7 3 15 8 1 [出力例] 24 [入力例] 25 70 77 52 10 56 11 95 86 93 7 66 74 114 8 4 1 66 2 34 35 8 42 55 74 60 [出力例] 200 [入力例] 100 89 161 141 234 1 38 245 4 22 15 12 16 123 33 65 201 114 174 155 150 121 245 161 146 23 7 13 191 178 193 53 7 221 122 244 86 174 150 116 98 24 8 14 112 185 9 168 10 96 58 176 201 179 8 17 210 155 72 208 151 217 240 96 22 215 18 190 178 123 50 73 233 117 20 111 88 6 208 126 2 210 11 178 19 35 3 215 224 171 223 5 108 12 85 168 21 239 51 256 216 [出力例] 500 |
■C++版プログラム(問題D/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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vs = vector<set<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 a first #define b second int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); // 2. 距離の二乗が M のベクトルは? // -> すべての頂点に対して, 二点間の距離を計算すると, 計算量が, N の 4乗くらいになりそうなので, // 原点から, 距離の二乗が M のベクトルだけ, 保存する方針とした. set<P> st; rep(i, N){ rep(j, N){ if(i * i + j * j == M){ st.insert({-i, -j}); st.insert({-i, +j}); st.insert({+i, -j}); st.insert({+i, +j}); } } } // 3. グラフ作成. // -> 距離の二乗が, M となるマス間に, 辺を張る. int n = N * N; vs G(n); rep(i, N){ rep(j, N){ int p1 = i * N + j; for(auto &v : st){ int r = i + v.a; int c = j + v.b; if(r >= 0 && r <= N - 1 && c >= 0 && c <= N - 1){ int p2 = r * N + c; G[p1].insert(p2); G[p2].insert(p1); } } } } // 4. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](vs &G, int s, int* d){ // 空のキュー. queue<int> q; // スタート地点は, 距離ゼロ. d[s] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. int u = q.front(); q.pop(); // 隣接頂点をチェック. for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v); } }; int d[n]; rep(i, n) d[i] = -1; bfs(G, 0, d); // 5. 出力. rep(i, N) rep(j, N) printf("%d%s", d[i * N + j], (j < N - 1) ? " " : "\n"); 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 |
[入力例] 3 1 [出力例] 0 1 2 1 2 3 2 3 4 ※AtCoderテストケースより [入力例] 10 5 [出力例] 0 3 2 3 2 3 4 5 4 5 3 4 1 2 3 4 3 4 5 6 2 1 4 3 2 3 4 5 4 5 3 2 3 2 3 4 3 4 5 6 2 3 2 3 4 3 4 5 4 5 3 4 3 4 3 4 5 4 5 6 4 3 4 3 4 5 4 5 6 5 5 4 5 4 5 4 5 6 5 6 4 5 4 5 4 5 6 5 6 7 5 6 5 6 5 6 5 6 7 6 ※AtCoderテストケースより [入力例] 5 5 [出力例] 0 3 2 3 2 3 4 1 2 3 2 1 4 3 2 3 2 3 2 3 2 3 2 3 4 [入力例] 7 2 [出力例] 0 -1 2 -1 4 -1 6 -1 1 -1 3 -1 5 -1 2 -1 2 -1 4 -1 6 -1 3 -1 3 -1 5 -1 4 -1 4 -1 4 -1 6 -1 5 -1 5 -1 5 -1 6 -1 6 -1 6 -1 6 [入力例] 25 34 [出力例] 0 -1 6 -1 4 -1 2 -1 8 -1 2 -1 4 -1 6 -1 4 -1 6 -1 4 -1 6 -1 8 -1 5 -1 3 -1 5 -1 3 -1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 5 -1 5 -1 6 -1 4 -1 4 -1 6 -1 2 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 6 -1 3 -1 7 -1 1 -1 5 -1 5 -1 3 -1 7 -1 3 -1 5 -1 7 -1 5 -1 7 -1 4 -1 4 -1 6 -1 4 -1 4 -1 4 -1 4 -1 6 -1 4 -1 4 -1 6 -1 6 -1 6 -1 5 -1 1 -1 7 -1 3 -1 3 -1 7 -1 3 -1 5 -1 5 -1 5 -1 7 -1 5 -1 2 -1 6 -1 4 -1 4 -1 6 -1 2 -1 6 -1 6 -1 4 -1 6 -1 4 -1 6 -1 6 -1 3 -1 5 -1 3 -1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 7 -1 5 -1 5 -1 8 -1 2 -1 4 -1 6 -1 2 -1 6 -1 4 -1 4 -1 8 -1 4 -1 6 -1 6 -1 6 -1 5 -1 5 -1 3 -1 5 -1 5 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1 2 -1 6 -1 4 -1 2 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 6 -1 8 -1 5 -1 3 -1 7 -1 3 -1 5 -1 7 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1 4 -1 4 -1 4 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 3 -1 7 -1 3 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 6 -1 4 -1 6 -1 6 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 5 -1 3 -1 5 -1 5 -1 3 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 4 -1 6 -1 4 -1 4 -1 8 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8 -1 5 -1 5 -1 5 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 6 -1 4 -1 4 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8 -1 6 -1 5 -1 7 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1 4 -1 6 -1 6 -1 4 -1 6 -1 6 -1 4 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8 -1 5 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1 7 -1 6 -1 6 -1 6 -1 6 -1 6 -1 6 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8 -1 8 -1 5 -1 7 -1 5 -1 5 -1 7 -1 5 -1 7 -1 7 -1 5 -1 9 -1 7 -1 7 -1 8 -1 6 -1 6 -1 6 -1 6 -1 8 -1 6 -1 6 -1 8 -1 6 -1 8 -1 8 -1 6 |
■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 |
// 解き直し. // https://atcoder.jp/contests/abc272/editorial/4982 // 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[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%lld", &a[i]); // 2. 各A[i]の操作で得られる値. set<LL> op[M + 1]; LL q = 0, r = 0; repx(i, 1, N + 1){ // 負. if(a[i - 1] < 0){ // 下限. LL l = abs(a[i - 1]) / i + ((abs(a[i - 1]) % i) > 0); l = min(l, (LL)M); // 上限. LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0); r = min(r, (LL)M); // 保存. repx(j, (int)l, (int)(r + 1)) op[j].insert(j * i + a[i - 1]); // 次へ. continue; } // 上記以外. // 次へ. if(a[i - 1] > N) continue; // 下限(ゼロ). // 上限. LL r = (N - a[i - 1]) / i + (((N - a[i - 1]) % i) > 0); r = min(r, (LL)M); // 保存. rep(j, (int)(r + 1)) op[j].insert(j * i + a[i - 1]); } // 3. 出力. repx(i, 1, M + 1){ if(op[i].empty()){ puts("0"); continue; } int ans = -1; while(op[i].count(++ans)){} 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 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 |
[入力例] 3 3 -1 -1 -6 [出力例] 2 2 0 ※AtCoderテストケースより [入力例] 5 6 -2 -2 -5 -7 -15 [出力例] 1 3 2 0 0 0 ※AtCoderテストケースより [入力例] 7 8 -5 -10 -14 -8 -17 -20 -25 [出力例] 0 1 0 0 2 0 0 0 [入力例] 15 10 -2 -2 -5 -12 -20 -30 -42 -56 -60 -70 -100 -101 -102 -150 -225 [出力例] 1 3 2 1 1 1 1 0 0 0 [入力例] 30 20 -20 -38 -56 -72 -89 -106 -98 -104 -108 -10 -11 -11 -13 -27 -28 -64 -85 -90 -190 -20 -21 -43 -45 -44 -220 -256 -267 -278 -289 -300 [出力例] 2 0 0 1 1 0 0 0 0 5 0 1 1 1 0 0 0 3 2 1 |
■参照サイト
AtCoder Beginner Contest 272