C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題C (ℕ Coloring) を解いてみた.
■感想.
1. 規則性が抽出出来たので, 久しぶりに, 解答見る前に, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 115 解説 の 各リンク を ご覧下さい.
■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 |
// 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 ans[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. i の 小さい順に, 数列を更新. rep(i, 101010) ans[i] = 1; repx(i, 1, N + 1) repex(j, i * 2, N + 1, i) if(ans[i] == ans[j]) ans[j]++; // 3. 出力. repx(i, 1, N + 1){ printf("%d", ans[i]); printf("%s", (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 |
[入力例] 4 [出力例] 1 2 2 3 ※AtCoderのテストケースより [入力例] 7 [出力例] 1 2 2 3 2 3 2 [入力例] 77 [出力例] 1 2 2 3 2 3 2 4 3 3 2 4 2 3 3 5 2 4 2 4 3 3 2 5 3 3 4 4 2 4 2 6 3 3 3 5 2 3 3 5 2 4 2 4 4 3 2 6 3 4 3 4 2 5 3 5 3 3 2 5 2 3 4 7 3 4 2 4 3 4 2 6 2 3 4 4 3 [入力例] 777 [出力例] 1 2 2 3 2 3 2 4 3 3 2 4 2 3 3 5 2 4 2 4 3 3 2 5 3 3 4 4 2 4 2 6 3 3 3 5 2 3 3 5 2 4 2 4 4 3 2 6 3 4 3 4 2 5 3 5 3 3 2 5 2 3 4 7 3 4 2 4 3 4 2 6 2 3 4 4 3 4 2 6 5 3 2 5 3 3 3 5 2 5 3 4 3 3 3 7 2 4 4 5 2 4 2 5 4 3 2 6 2 4 3 6 2 4 3 4 4 3 3 6 3 3 3 4 4 5 2 8 3 4 2 5 3 3 5 5 2 4 2 5 3 3 3 7 3 3 4 4 2 5 2 5 4 4 3 5 2 3 3 7 3 6 2 4 4 3 2 6 3 4 4 4 2 4 4 6 3 3 2 6 2 4 3 5 3 4 3 4 5 4 2 8 2 3 4 5 2 5 2 6 3 3 3 5 3 3 4 6 3 5 2 4 3 3 3 7 3 3 3 5 3 4 2 7 5 3 2 5 2 4 4 5 2 5 3 4 3 4 2 7 2 4 6 4 4 4 3 5 3 5 2 6 3 3 4 9 2 4 3 5 4 3 2 6 3 4 3 4 2 6 2 6 4 3 4 5 2 3 4 6 2 4 2 4 4 4 3 8 3 4 3 4 2 5 3 5 5 3 3 6 3 3 3 6 3 5 2 5 3 4 2 6 2 3 5 4 2 4 3 8 3 4 3 7 4 3 3 5 3 5 2 4 4 3 3 7 2 4 3 5 3 5 4 5 4 3 2 5 2 5 5 7 2 4 3 4 4 3 2 7 3 3 4 5 3 4 2 6 4 4 3 5 2 4 5 5 3 6 2 5 3 3 2 9 4 3 4 4 2 5 3 6 3 3 3 6 2 3 4 7 2 4 3 4 6 4 3 6 2 4 3 4 3 5 3 7 3 4 2 6 2 3 4 5 4 4 3 4 4 4 2 8 2 4 4 4 3 4 2 6 5 4 2 5 3 3 3 8 2 6 3 4 3 3 4 6 2 3 5 5 2 5 2 6 4 3 2 6 3 4 3 5 3 4 4 5 4 3 2 8 3 3 4 5 3 7 2 5 3 5 2 5 3 4 5 6 3 4 2 6 3 3 2 7 3 4 4 4 2 5 3 10 5 3 3 5 3 4 3 6 2 5 2 4 5 3 3 7 3 4 4 5 3 4 3 5 3 3 4 7 2 3 3 7 3 5 2 4 4 5 3 6 3 3 4 4 2 5 3 7 4 3 2 5 3 3 6 5 2 5 2 5 3 4 4 9 2 4 3 5 3 4 3 5 5 3 2 6 3 4 3 6 2 6 4 4 3 4 2 7 2 4 4 4 4 4 2 7 4 4 3 6 2 3 4 6 2 4 2 5 5 3 3 7 5 3 4 4 3 6 2 5 3 3 3 5 4 4 4 9 2 4 2 5 4 4 2 8 3 5 4 4 2 4 3 6 4 4 2 6 2 3 4 5 4 5 3 4 3 4 3 8 2 3 6 5 2 4 3 6 3 4 2 6 3 5 3 6 3 5 2 4 5 3 3 6 3 3 3 6 2 6 3 8 4 3 3 5 2 4 4 5 3 5 4 4 3 3 2 8 3 4 3 4 4 5 2 6 7 4 3 5 2 3 5 7 3 5 2 5 4 4 2 6 3 3 4 5 3 6 2 6 3 4 3 7 2 3 4 6 2 4 3 4 5 3 3 10 2 5 3 4 2 5 4 5 4 |
■参照サイト
AtCoder Regular Contest 115