C++の練習を兼ねて, AtCoder Regular Contest 118 の 問題C (Coprime Set) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 解説のロジックで, 条件を満たす整数を抽出できる点が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 118 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc118/editorial/1206 // 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 N; scanf("%d", &N); // 2. 基準とする集合. set<int> st = {6, 10, 15}; // 3. 6 の 倍数. int n = 1; while(st.size() < N && (n + 1) * 6 <= 10000) st.insert(++n * 6); // 4. 10 の 倍数. n = 1; while(st.size() < N && (n + 1) * 10 <= 10000) st.insert(++n * 10); // 5. 15 の 倍数. n = 1; while(st.size() < N && (n + 1) * 15 <= 10000) st.insert(++n * 15); // 6. 最大公約数チェック. int g = 6; vi ans; for(auto &p : st){ ans.pb(p); g = __gcd(g, p); } assert(g == 1); // 7. 出力. rep(i, N) printf("%d%s", ans[i], (i < 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 |
[入力例] 4 [出力例] 84 60 105 70 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 6 10 12 15 [入力例] 3 [出力例] 6 10 15 [入力例] 5 [出力例] 6 10 12 15 18 [入力例] 10 [出力例] 6 10 12 15 18 24 30 36 42 48 [入力例] 15 [出力例] 6 10 12 15 18 24 30 36 42 48 54 60 66 72 78 [入力例] 100 [出力例] 6 10 12 15 18 24 30 36 42 48 54 60 66 72 78 84 90 96 102 108 114 120 126 132 138 144 150 156 162 168 174 180 186 192 198 204 210 216 222 228 234 240 246 252 258 264 270 276 282 288 294 300 306 312 318 324 330 336 342 348 354 360 366 372 378 384 390 396 402 408 414 420 426 432 438 444 450 456 462 468 474 480 486 492 498 504 510 516 522 528 534 540 546 552 558 564 570 576 582 588 |
■参照サイト
AtCoder Regular Contest 118