C++の練習を兼ねて, AtCoder Regular Contest 117 の 問題A (God Sequence) ~ 問題C (Tricolor Pyramid) を解いてみた.
■感想.
1. 問題B, Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 117 解説 の 各リンクを ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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 int main(){ // 1. 入力情報. int A, B; scanf("%d %d", &A, &B); // 2. 数列を計算. vi ans; if(A > B){ rep(i, A) ans.pb(i + 1); rep(i, B - 1) ans.pb(-i - 1); ans.pb(-(1 + A) * A / 2 + (B - 1) * B / 2); } if(A <= B){ rep(i, B) ans.pb(-i - 1); rep(i, A - 1) ans.pb(i + 1); ans.pb((1 + B) * B / 2 - (A - 1) * A / 2); } // 3. 出力. int l = ans.size(); rep(i, l){ printf("%d", ans[i]); printf("%s", (i < l - 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 |
[入力例] 1 1 [出力例] 1001 -1001 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. -1 1 [入力例] 1 4 [出力例] -8 -6 -9 120 -97 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. -1 -2 -3 -4 10 [入力例] 7 5 [出力例] -8 -6 -9 120 -97 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 1 2 3 4 5 6 7 -1 -2 -3 -4 -18 [入力例] 12 10 [出力例] 1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -33 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc117/editorial/1111 // 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--) const LL MOD = 1e9 + 7; LL a[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. sort. sort(a, a + N); // 3. ビルの景観の数は? LL ans = a[0] + 1; rep(i, N - 1){ ans *= (a[i + 1] - a[i] + 1); ans %= MOD; } // 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 23 24 25 26 27 28 29 30 |
[入力例] 2 1 2 [出力例] 4 ※AtCoderのテストケースより [入力例] 6 5 3 4 1 5 2 [出力例] 32 ※AtCoderのテストケースより [入力例] 7 314 159 265 358 979 323 846 [出力例] 492018656 ※AtCoderのテストケースより [入力例] 12 5 103 20 90 40 24 11 70 121 54 21 32 [出力例] 672866091 |
■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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
// 解き直し. // https://atcoder.jp/contests/arc117/editorial/1113 // 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--) const int LIMIT = 404040; int a[LIMIT], b[LIMIT], f[LIMIT], g[LIMIT], combination[LIMIT]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); char c[404040]; scanf("%s", c); // 2. f, g を 計算. b[0] = 1, g[0] = 1; repx(i, 1, N){ int idx = 0, q = i; while(q % 3 == 0) q /= 3, idx++; a[i] = idx; b[i] = q; } rep(i, N - 1) f[i + 1] = f[i] + a[i + 1]; rep(i, N - 1) g[i + 1] = g[i] * b[i + 1], g[i + 1] %= 3; rep(i, N){ if(f[N - 1] - f[i] - f[N - 1 - i] == 0){ if(g[N - 1] == 1){ if(g[i] * g[N - 1 - i] == 1) combination[i] = 1; if(g[i] * g[N - 1 - i] == 2) combination[i] = 2; if(g[i] * g[N - 1 - i] == 4) combination[i] = 1; } if(g[N - 1] == 2){ if(g[i] * g[N - 1 - i] == 1) combination[i] = 2; if(g[i] * g[N - 1 - i] == 2) combination[i] = 1; if(g[i] * g[N - 1 - i] == 4) combination[i] = 2; } } } // 3. 初期化. map<int, char> ans; ans[0] = 'R'; ans[1] = 'W'; ans[2] = 'B'; // 4. 集計. int t = 0; rep(i, N){ if(c[i] == 'R') t += 0 * combination[i]; if(c[i] == 'W') t += 1 * combination[i]; if(c[i] == 'B') t += 2 * combination[i]; t %= 3; } if(!(N & 1)) t *= -1; t = (t + 3) % 3; // 5. 出力. printf("%c\n", ans[t]); 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 |
[入力例] 3 BWR [出力例] W ※AtCoderのテストケースより [入力例] 4 RRBB [出力例] W ※AtCoderのテストケースより [入力例] 6 BWWRBW [出力例] B ※AtCoderのテストケースより [入力例] 8 WWBRBBWB [出力例] R ※AtCoderのテストケースより [入力例] 21 BWBRRBBRWBRBBBRRBWWWR [出力例] B ※AtCoderのテストケースより [入力例] 50 BBRBRGBBBGBRGRRBBGRRGRBRGBRRRGBGRRBBRGBGGGBRGGBRBR [出力例] R [入力例] 100 RGRBGGGGRRGBBRBBRRRBRBRBGGRGGRRGRRRRRBGRRBGRRRRGGRRGBGRBGRRBBRGRGBRRBBRRRRRGBRGGGBRBRRBBGRGRGBGBBRGB [出力例] B |
■参照サイト
AtCoder Regular Contest 117