C++の練習を兼ねて, AtCoder Regular Contest 111 の 問題E (Simple Math 3) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 下記のライブラリを拝借させて頂いた.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Regular Contest 111 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E／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 |
// 解き直し. // https://atcoder.jp/contests/arc111/editorial/494 // 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--) // AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp) // -> 一部改変(2021/01/19). LL floor_sum(LL n, LL m, LL a, LL b){ LL ans = 0; if(a >= m){ ans += (n - 1) * n * (a / m) / 2; a %= m; } if(b >= m){ ans += n * (b / m); b %= m; } LL y_max = (a * n + b) / m, x_max = (y_max * m - b); if(y_max == 0) return ans; ans += (n - (x_max + a - 1) / a) * y_max; ans += floor_sum(y_max, a, m, (a - x_max % a) % a); return ans; } int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. クエリ回答. rep(i, T){ // 2-1. 数式の構成要素を取得. LL A, B, C, D; scanf("%lld %lld %lld %lld", &A, &B, &C, &D); // 2-2. K を 計算. LL K = (D - 2) / (C - B); // 2-3. 与式の各項を計算. LL acd = floor_sum(K + 1, D, C, A); LL abd = floor_sum(K + 1, D, B, A - 1); LL ans = K - acd + abd; // 2-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 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 |
[入力例] 2 3 1 2 5 99 101 103 105 [出力例] 1 25 ※AtCoderのテストケースより [入力例] 15 3 8 11 13 1 3 9 12 5 1 7 8 6 9 20 22 3 6 15 23 4 4 16 17 12 11 22 32 12 1 10 18 6 7 19 26 12 11 19 20 3 9 15 20 3 11 18 25 2 4 10 17 1 4 7 8 2 9 11 17 [出力例] 2 1 0 0 1 0 1 0 1 1 2 1 1 1 3 [入力例] 30 15 61 117 191 20 58 139 151 101 107 205 269 93 54 103 121 33 48 68 166 105 50 172 275 40 7 88 140 89 7 79 145 111 14 51 156 26 115 168 280 84 32 33 89 39 29 86 135 107 51 174 227 56 82 194 290 32 120 156 167 13 107 181 214 62 110 114 175 71 85 124 233 68 120 204 215 26 120 222 335 94 79 102 216 15 14 22 114 75 35 82 115 12 98 217 280 24 116 239 268 10 9 106 144 96 4 62 152 65 17 43 106 116 39 48 117 112 60 153 273 [出力例] 2 0 1 1 3 0 1 0 0 2 43 1 0 1 2 2 21 4 0 1 4 6 0 1 1 1 0 1 4 1 |
■参照サイト
AtCoder Regular Contest 111
ac-library/atcoder/math.hpp