C++の練習を兼ねて, AtCoder Regular Contest 107 の 問題A (Simple Math) ～ 問題B (Quadruple) を解いてみた.
■感想.
1. B問題は, 正しく集計できるまでに, 時間かかったものの, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 107 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 998244353; int main(){ // 1. 入力情報. LL A, B, C; scanf("%lld %lld %lld", &A, &B, &C); // 2. 数式を計算. // 2-1. Σa. LL ans = 1; ans *= (1 + A); ans %= MOD; ans *= A; ans %= MOD; ans *= 499122177; ans %= MOD; // 2-2. Σb. ans *= (1 + B); ans %= MOD; ans *= B; ans %= MOD; ans *= 499122177; ans %= MOD; // 2-3. Σc. ans *= (1 + C); ans %= MOD; ans *= C; ans %= MOD; ans *= 499122177; ans %= MOD; // 3. 出力. 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 |
[入力例] 1 2 3 [出力例] 18 ※AtCoderのテストケースより [入力例] 1000000000 987654321 123456789 [出力例] 951633476 ※AtCoderのテストケースより [入力例] 314159265 358979323 846264338 [出力例] 72400245 |
■C++版プログラム(問題B／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 |
// 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--) LL ab[303030], cd[303030]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); // 2. (a + b) = K + (c + d) となる組み合わせを集計. // 2-1. a + b の 組み合わせ. int sab = 2; int gab = min(K + 2 * N, 2 * N); repx(i, sab, gab + 1){ // ex. // i = N => (N - 1)通り. // i = N + 1 => N通り. // i = N + 2 => (N - 1)通り. ab[i] = (i > N) ? 2 * N + 1 - i : i - 1; ab[i] = max(0LL, ab[i]); } // 2-2. c + d の 組み合わせ. int scd = 2; int gcd = min(2 * N - K, 2 * N); repx(i, scd, gcd + 1){ cd[i] = (i > N) ? 2 * N + 1 - i : i - 1; cd[i] = max(0LL, cd[i]); } // 3. 集計. // ※ c + d は, インデックス を K ずらしたものを取得. LL ans = 0; rep(i, 303030){ int j = i - K; if(j >= 0 && j < 303030) ans += ab[i] * cd[j]; } // 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 |
[入力例] 2 1 [出力例] 4 ※AtCoderのテストケースより [入力例] 2525 -425 [出力例] 10314607400 ※AtCoderのテストケースより [入力例] 2 0 [出力例] 6 [入力例] 3 0 [出力例] 19 [入力例] 3 1 [出力例] 16 [入力例] 3 2 [出力例] 10 [入力例] 3 3 [出力例] 4 [入力例] 3 4 [出力例] 1 [入力例] 31415 9265 [出力例] 18370006445360 [入力例] 31415 -9265 [出力例] 18370006445360 [入力例] 98765 43210 [出力例] 498204703553400 |
■参照サイト
AtCoder Regular Contest 107