C++の練習を兼ねて, AtCoder Beginner Contest 238 の 問題C (digitnum) ~ 問題D (AND and SUM) を解いてみた.
■感想.
1. 問題C, Dは, 方針が絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 238 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/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 |
// 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 MOD = 998244353; int main(){ // 1. 入力情報. LL N; scanf("%lld", &N); // 2. Σf(x). // ex. // N = 1234 // 4桁 … 1000 ~ 1234 から, (1 + 235) * 235 / 2 = 27730. // 3桁 … 100 ~ 999 から, (1 + 900) * 900 / 2 = 405450. // 2桁 … 10 ~ 99 から, (1 + 90) * 90 / 2 = 4095. // 1桁 … 1 ~ 9 から, (1 + 9) * 9 / 2 = 45. // -> 合計 437320 の はず. auto sf = [&](LL x) -> LL { // 2-1. 10 の 冪乗. vl cPow10; cPow10.pb(1); while(cPow10.size() <= 18) cPow10.pb(10 * cPow10.back()); // 2-2. 各桁ごとに集計. LL ret = 0, cur = x; repr(i, cPow10.size() - 1, 0){ if(cPow10[i] <= cur){ // cur と 桁数 が 同じものがいくつあるか? LL t = (cur - cPow10[i] + 2) % MOD; t *= (cur - cPow10[i] + 1) % MOD; t %= MOD; t *= 499122177; t %= MOD; // 集計. ret += t; ret %= MOD; // 次へ. cur = cPow10[i] - 1; } } // 2-3. 返却. return ret; }; // 3. 出力. printf("%lld\n", sf(N)); 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 |
[入力例] 16 [出力例] 73 ※AtCoderテストケースより [入力例] 238 [出力例] 13870 ※AtCoderテストケースより [入力例] 999999999999999999 [出力例] 762062362 ※AtCoderテストケースより [入力例] 99 [出力例] 4140 [入力例] 1234 [出力例] 437320 [入力例] 2022 [出力例] 933366 [入力例] 20220206 [出力例] 216690071 |
■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 |
// 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--) int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. クエリ回答. rep(i, T){ // 2-1. クエリ入力情報. LL a, s; scanf("%lld %lld", &a, &s); // 2-2. 条件を満たす 非負整数の組 (x, y) が 存在するか? bool ok = false; if(a <= s){ LL x = a; LL y = s - a; ok = ((x & y) == a); } // 2-3. 出力. printf("%s\n", ok ? "Yes" : "No"); } 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 |
[入力例] 2 1 8 4 2 [出力例] Yes No ※AtCoderテストケースより [入力例] 4 201408139683277485 381410962404666524 360288799186493714 788806911317182736 18999951915747344 451273909320288229 962424162689761932 1097438793187620758 [出力例] No Yes Yes No ※AtCoderテストケースより [入力例] 5 7 5 6 13 9 5 2 7 4 11 [出力例] No Yes No No Yes [入力例] 7 1 4 3 14 10 20 18 36 5 50 38 93 37 156 [出力例] Yes Yes Yes Yes Yes Yes Yes |