C++の練習を兼ねて, 競プロ典型 90 問 の 問題058 (Original Calculator) を解いてみた.
■感想.
1. 問題058は, 実装に苦労したものの, 周期を抽出できたので, AC版に到達出来たと思う.
2. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題058 を ご覧下さい.
■C++版プログラム(問題058/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 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) // const int MOD = 1000; const int MOD = 100000; int memo[101010]; int main(){ // 1. 入力情報. int N; LL K; scanf("%d %lld", &N, &K); // 2. ボタン A を 押下. // 2-1. 指定回数実行. auto f = [](int n, int u) -> int{ // 終了条件. if(u <= 0) return n; // 初回処理. string sn = to_string(n); int cur = n, c = 1; rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; // 繰り返し処理. while(c < u){ // 各桁の和. sn = to_string(cur); // 今回分更新. rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; // インクリメント. c++; } // 出力. return cur; }; // 2-2. 周期(同じ整数が出現した時の整数は?). auto g = [&](int n) -> int{ // 基準となる整数. memo[n]++; // 初回処理. string sn = to_string(n); int cur = n; rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; memo[cur]++; // 繰り返し処理. while(memo[cur] < 2){ sn = to_string(cur); rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; memo[cur]++; } // 出力. return cur; }; // 2-3. 周期(指定された整数 t が, 最初に出現するまでの操作回数は?). auto h = [&](int n, int t) -> int{ // 終了条件. LL c = 0; if(n == t) return c; // 初回処理. string sn = to_string(n); int cur = n; rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; memo[cur]++; c++; // 繰り返し処理. while(cur != t){ sn = to_string(cur); rep(i, sn.size()) cur += sn[i] - '0'; cur %= MOD; memo[cur]++; c++; } // 出力. return c; }; // 3. ボタン A 押下時の挙動. // 3-1. 初めて同じ整数が, 二回出現するケースを確認. int x = g(N); LL f2 = 0; rep(i, 101010) if(memo[i]) f2++; // 3-2. 前項の整数が, 一回目出現するまでを確認. rep(i, 101010) memo[i] = 0; LL f1 = h(N, x); // 4. K回操作後の整数を算出. // 4-1. 周期 および K回操作の最小化. LL f3 = f2 - f1; if(K > f1) K = f1 + (K - f1) % f3; // 4-2. 整数を取得. int ans = f(N, (int)K); // 5. 出力. printf("%d\n", ans); 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 |
[入力例] 5 3 [出力例] 13 ※AtCoderテストケースより [入力例] 0 100 [出力例] 0 ※AtCoderテストケースより [入力例] 99999 1000000000000000000 [出力例] 84563 ※AtCoderテストケースより [入力例] 12 345 [出力例] 5055 [入力例] 123 9876543210 [出力例] 16555 [入力例] 31415 926535897932 [出力例] 26057 |
■参照サイト
058 – Original Calculator