C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題F (Problem where +s Separate Digits) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 確率, 期待値の考え方で, 解いていく方針が, 不思議な印象を受けたとともに, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 224 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F／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 |
// 解き直し. // https://atcoder.jp/contests/abc224/editorial/2805 // 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 LL MOD = 998244353; LL mPowP2[202020], mPowM2[202020], mPow10[202020], mCum[202020]; int main(){ // 1. 入力情報. char c[202020]; scanf("%s", c); string s(c); int N = s.size(); // 2. 例外. if(N == 1){ printf("%s\n", s.c_str()); return 0; } // 3. 2, 10 の 冪乗. mPowP2[0] = mPowM2[0] = mPow10[0] = 1; rep(i, N + 1){ mPowP2[i + 1] = (2 * mPowP2[i]) % MOD; mPowM2[i + 1] = (499122177 * mPowM2[i]) % MOD; mPow10[i + 1] = (10 * mPow10[i]) % MOD; } // 4. 累積和. // ex. // k = 1 -> 0 + (+ 1 * 1 / 1) // k = 2 -> 1 * 1 / 2 (+ 10 * 1 / 2) // k = 3 -> 1 * 1 / 2 + 10 * 1 / 4 (+ 100 * 1 / 4) // k = 4 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 (+ 1000 * 1 / 8) // k = 5 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 + 1000 * 1 / 16 (+ 10000 * 1 / 16) // ... // -> 例外部分は, 後述の集計時に考慮すれば十分のはず. repx(i, 2, N + 1){ mCum[i] += mCum[i - 1]; mCum[i] %= MOD; mCum[i] += mPowM2[i - 1] * mPow10[i - 2]; mCum[i] %= MOD; } // 5. 文字列 S の 各文字について, 集計. // -> 文字列 S の 右から k文字目 を x と 見て計算. LL ans = 0; repx(k, 1, N + 1){ // 等比数列の和. int i = N - k; LL x = (LL)(s[i] - '0'); ans += x * mCum[k]; ans %= MOD; // 例外. ans += x * mPowM2[k - 1] * mPow10[k - 1]; ans %= MOD; } // 6. 2 の |S| - 1 乗 を 乗ずる. ans *= mPowP2[N - 1]; ans %= MOD; // 7. 出力. 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 |
[入力例] 1234 [出力例] 1736 ※AtCoderテストケースより [入力例] 1 [出力例] 1 ※AtCoderテストケースより [入力例] 31415926535897932384626433832795 [出力例] 85607943 ※AtCoderテストケースより [入力例] 11 [出力例] 13 [入力例] 111 [出力例] 138 [入力例] 2021 [出力例] 2344 [入力例] 20211101 [出力例] 23511616 [入力例] 2236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274 [出力例] 83041925 |
■参照サイト
AtCoder Beginner Contest 224