C++の練習を兼ねて, AtCoder Beginner Contest 234 の 問題E (Arithmetic Number) を解いてみた.
■感想.
1. 問題Eは, 規則性を見つけることが出来たので, AC版に到達できたと思う.
2. 等差数を, 抽出してところ, 意外と少なく(ここでは, 339個だった), 非常に面白い問題と感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 234 解説 の 各リンク を ご覧下さい.
■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 |
// 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 main(){ // 1. 入力情報. LL X; scanf("%lld", &X); // 2. 等差数作成. vl aNumber; rep(i, 9) aNumber.pb(i + 1); repx(k, 2, 19){ // 等差数が, k桁だったと仮定. // -> 初項 s, 公差 t で, k項 の 等差数列 が 存在するか？ repx(s, 1, 10){ repx(t, -9, 10){ // 初項. string seq; seq.pb(s + '0'); // 残りの項. int d = s; bool ok = true; rep(i, k - 1){ d += t; if(d < 0 || d > 9){ ok = false; break; } seq.pb(d + '0'); } // 保存. if(ok) aNumber.pb(stoll(seq)); } } } // for(auto &p : aNumber) printf("%lld\n", p); // 3. sort. sort(all(aNumber)); // 4. 位置検索. int at = lower_bound(all(aNumber), X) - aNumber.begin(); // 5. 出力. printf("%lld\n", aNumber[at]); 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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
[入力例] 152 [出力例] 159 ※AtCoderテストケースより [入力例] 88 [出力例] 88 ※AtCoderテストケースより [入力例] 8989898989 [出力例] 9876543210 ※AtCoderテストケースより [入力例] 51 [出力例] 51 [入力例] 100 [出力例] 111 [入力例] 112 [出力例] 123 [入力例] 964 [出力例] 975 [入力例] 1248 [出力例] 1357 [入力例] 1234 [出力例] 1234 [入力例] 3141 [出力例] 3210 [入力例] 12321 [出力例] 12345 [入力例] 526718 [出力例] 543210 [入力例] 20220110 [出力例] 22222222 [入力例] 53536007464846939 [出力例] 55555555555555555 [入力例] 100000000000000000 [出力例] 111111111111111111 |
■参照サイト
AtCoder Beginner Contest 234