C++の練習を兼ねて, AtCoder Regular Contest 084 の 問題E (Finite Encyclopedia of Integer Sequences)を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 084 解説 を ご覧下さい.
■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 68 69 70 71 72 73 74 75 76 77 |
// 解き直し. // https://img.atcoder.jp/arc084/editorial.pdf // 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 pof pop_front #define pob pop_back #define pub push_back #define puf push_front int main(){ // 1. 入力情報. int K, N; scanf("%d %d", &K, &N); // 2. K が 偶数 の 場合. if(!(K & 1)){ // 2-1. K / 2 追加. vi ans; ans.pub(K / 2); // 2-2. K 追加. rep(i, N - 1) ans.pub(K); // 2-3. 出力. rep(i, N){ printf("%d", ans[i]); printf("%s", (i < N - 1) ? " " : "\n"); } } // 3. K が 奇数 の 場合. if(K & 1){ // 3-1. 数列 B を 作成. vi ans; int k = (K + 1) / 2; rep(i, N) ans.pub(k); // 3-2. B の ((N - 1) / 2)個手前の数列 を 計算. int n = (N - 1) / 2; // N が 偶数の場合, 切り上げ. if(!(N & 1)) n++; while(n){ // 末尾の要素を取得. int last = ans.back(); // 末尾 が 1 の 場合. if(last == 1) ans.pob(); // 末尾 が 1 でない場合. if(last != 1){ // 1 減少. ans.back()--; // N 文字になるまで, K を 追加. while(ans.size() < N) ans.pub(K); } // デクリメント. n--; } // 3-3. 出力. rep(i, ans.size()){ printf("%d", ans[i]); printf("%s", (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 40 41 42 43 44 |
[入力例] 3 2 [出力例] 2 1 ※AtCoderのテストケースより [入力例] 2 4 [出力例] 1 2 2 2 ※AtCoderのテストケースより [入力例] 5 14 [出力例] 3 3 3 3 3 3 3 3 3 3 3 3 2 2 ※AtCoderのテストケースより [入力例] 10 5 [出力例] 5 10 10 10 10 [入力例] 11 7 [出力例] 6 6 6 6 6 6 3 [入力例] 2021 33 [出力例] 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 1011 995 [入力例] 3 101 [出力例] 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 3 1 |
■参照サイト
AtCoder Regular Contest 084