C++の練習を兼ねて, AtCoder Regular Contest 099 の 問題D (Snuke Numbers) を解いてみた.
■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 条件を整数の抽出方法が, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 099 解説 を ご覧下さい.
■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 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 93 |
// 解き直し. // https://img.atcoder.jp/arc099/editorial.pdf // 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 const LL INF = 202020202020202020; int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. 10の冪乗を用意. vl cPow; cPow.pb(1); while(cPow.back() < 1e18){ // 最大値を10倍. LL p = 10 * cPow.back(); // 保存. cPow.pb(p); } // for(auto &p : cPow) printf("%lld\n", p); // 3. x を保存. // -> N = 792 で, 丁度桁あふれするので, N / S(N) と x / S(x) を比較する部分を修正. int count = 0; LL N = 1; vl v; while(count < K){ // 3-1. N に 対する N / S(N) の 準備. string nStr = to_string(N); LL sn = 0; rep(j, nStr.size()) sn += (nStr[j] - '0'); // 3-2. x に 対する x / S(x) の 準備. int d = (int)log10(N) + 1; LL S = 0, X = 0, minS = INF, minX = INF; rep(j, d + 1){ X = cPow[j + 1] * (N / cPow[j + 1] + 1) - 1; string xStr = to_string(X); S = 0; rep(k, xStr.size()) S += (xStr[k] - '0'); // 初回確認時. if(minS == INF){ minS = S; minX = X; } // 2回目以降. if(minS < INF){ if(X * minS < minX * S){ minS = S; minX = X; } } } // printf("count=%d S=%lld X=%lld N=%lld\n", count, S, X, N); // 3-3. N に 対する N / S(N) と x に 対する x / S(x) を 比較. // 前者が小さい場合は, 追加. // if(N * minS <= minX * sn){ // N = 792 で 桁あふれ. if((double)N / (double)sn <= (double)minX / (double)minS){ // Snuke数 を 追加. v.pb(N); // インクリメント. N++; count++; // 次へ. continue; } // 3-4. 前者が大きい場合は, 追加しない. // if(N * minS > minX * sn) N = minX; // N = 792 で 桁あふれ. if((double)minS / (double)sn > (double)minX / (double)N) N = minX; } // 4. 出力. for(auto &p : v) printf("%lld\n", p); 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 93 94 95 96 97 |
[入力例] 10 [出力例] 1 2 3 4 5 6 7 8 9 19 ※AtCoderのテストケースより [入力例] 77 [出力例] 1 2 3 4 5 6 7 8 9 19 29 39 49 59 69 79 89 99 199 299 399 499 599 699 799 899 999 1099 1199 1299 1399 1499 1599 1699 1799 1899 1999 2999 3999 4999 5999 6999 7999 8999 9999 10999 11999 12999 13999 14999 15999 16999 17999 18999 19999 20999 21999 22999 23999 24999 25999 26999 27999 28999 29999 39999 49999 59999 69999 79999 89999 99999 109999 119999 129999 139999 149999 |
■参照サイト
AtCoder Regular Contest 099