C++の練習を兼ねて, AtCoder Beginner Contest 250 の 問題C (Adjacent Swaps) ~ 問題D (250-like Number) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 250 解説 の 各リンク を ご覧下さい.
■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 |
// 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 io[202020], oi[202020]; int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); rep(i, N){ io[i + 1] = i + 1; // 位置から見たボールの番号. oi[i + 1] = i + 1; // ボールの番号から見た位置. } // 2. 操作. rep(i, Q){ // ボール情報. int x; scanf("%d", &x); int pos1 = oi[x]; int pos2 = (pos1 == N) ? pos1 - 1 : pos1 + 1; int y = io[pos2]; // 操作. swap(io[pos1], io[pos2]); swap(oi[x], oi[y]); } // 4. 出力. repx(i, 1, N + 1) printf("%d%s", io[i], (i < N) ? " " : "\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 |
[入力例] 5 5 1 2 3 4 5 [出力例] 1 2 3 5 4 ※AtCoderテストケースより [入力例] 7 7 7 7 7 7 7 7 7 [出力例] 1 2 3 4 5 7 6 ※AtCoderテストケースより [入力例] 10 6 1 5 2 9 6 6 [出力例] 1 2 3 4 5 7 6 8 10 9 ※AtCoderテストケースより [入力例] 20 30 10 12 2 10 5 11 19 19 1 4 5 15 13 14 16 20 1 20 17 10 11 3 1 19 20 9 15 5 15 9 [出力例] 2 3 6 1 4 7 8 5 13 11 9 12 10 14 16 18 17 15 19 20 |
■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 |
// 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 #define all(x) x.begin(), x.end() int a[1010101]; int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. 素数を取得. repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) a[j]++; vl ps, qs; repx(i, 2, 1010101) if(!a[i]) ps.pb(i); for(auto &p : ps) qs.pb(p * p * p); qs.erase(qs.begin()); // 3. 集計. int ans = 0; for(auto &p : ps){ LL t = N / p; if(!t) break; int at = upper_bound(all(qs), t) - qs.begin(); ans += at; if(!qs.empty()) qs.erase(qs.begin()); } // 4. 出力. 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 |
[入力例] 250 [出力例] 2 ※AtCoderテストケースより [入力例] 1 [出力例] 0 ※AtCoderテストケースより [入力例] 123456789012345 [出力例] 226863 ※AtCoderテストケースより [入力例] 1029 [出力例] 5 [入力例] 2022 [出力例] 6 [入力例] 20220514 [出力例] 316 [入力例] 3141592653 [出力例] 2549 [入力例] 1000000000000000000 [出力例] 11871859 |
■参照サイト
AtCoder Beginner Contest 250