C++の練習を兼ねて, AtCoder Regular Contest 141 の 問題A (Periodic Number) を解いてみた.
■感想.
1. 問題Aは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 141 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 |
// 解き直し. // https://atcoder.jp/contests/arc141/editorial/4021 // 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 int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 10の冪乗. vl cPow; cPow.pb(1); while(cPow.back() < 1e18){ // 最大値を10倍. LL p = 10 * cPow.back(); // 保存. cPow.pb(p); } // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. LL N; scanf("%lld", &N); string s = to_string(N); int sl = s.size(); // 3-2. 例外. // -> 予め, 999...999 の ケース を 保存. LL ans = 0; for(auto &p : cPow) if(p <= N) ans = p - 1; // 3-3. 周期的な数は? for(auto &d : {1, 2, 3, 4, 5, 6, 7, 8, 9}){ // d 桁ずつ分けることができるか? if(sl % d) continue; // 2個以上に分割できるか? if((sl / d) < 2) continue; // パターン①. string c1 = s.substr(0, d); string sCur1 = ""; rep(i, sl / d) sCur1 += c1; LL cur1 = stoll(sCur1); if(cur1 <= N) ans = max(ans, cur1); // パターン②. string c2 = to_string(stoll(c1) - 1); string sCur2 = ""; rep(i, sl / d) sCur2 += c2; LL cur2 = stoll(sCur2); ans = max(ans, cur2); } // 3-4. 出力. printf("%lld\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 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 |
[入力例] 3 1412 23 498650499498649123 [出力例] 1313 22 498650498650498650 ※AtCoderのテストケースより [入力例] 12 11 12 100 1001 1010 2021 33333 100010 20220530 1110545233 176166110176166110 102030102030102030 [出力例] 11 11 99 999 1010 2020 33333 99999 20212021 1110511105 176166110176166110 102030102030102030 [入力例] 16 314 1592 65358 979323 8462643 38327950 288419716 9399375105 82097494459 230781640628 6208998628034 82534211706798 214808651328230 6647093844609550 58223172535940812 848111745028410270 [出力例] 222 1515 55555 978978 7777777 38323832 288288288 9399293992 77777777777 230781230781 5555555555555 82534208253420 214802148021480 6647093766470937 55555555555555555 848111744848111744 |
■参照サイト
AtCoder Regular Contest 141