C++の練習を兼ねて, AtCoder Beginner Contest 147 の 問題F (Sum Difference) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 数列に関する性質を学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 147 解説 を ご覧下さい.
■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 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
// 解き直し. // https://img.atcoder.jp/abc147/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<LL, LL>; using vp = vector<P>; using vvp = vector<vp>; #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 #define a first #define b second #define all(x) x.begin(), x.end() int main(){ // 1. 入力情報. LL N, X, D; scanf("%lld %lld %lld", &N, &X, &D); // 2. 例外. if(D == 0){ printf("%lld\n", (X == 0) ? 1LL : N + 1); return 0; } // 3. 符号調整. if(D < 0){ X *= -1; D *= -1; } // 4. 座標圧縮. // -> k * X mod D の 取り得る値を保存. map<LL, int> o; rep(k, N + 1) o[k * X % D] = 0; int idx = -1; for(auto &p : o) p.b = ++idx; // 5. 区間保存(k * X mod D ごと). vvp v(idx + 1); rep(k, N + 1){ // 区間[l, r] の 計算. LL l = k ? (LL)k * (LL)(k - 1) / 2 : 0; LL r = k ? (LL)(k * N) - (LL)k * (LL)(k + 1) / 2 : 0; l *= D; l += k * X; r *= D; r += k * X; // 保存. v[o[k * X % D]].pb({l, r}); } // 6. sort(k * X mod D ごと). rep(i, idx + 1){ // sort. sort(all(v[i])); // 番兵. P p = v[i].back(); v[i].pb({p.b + 202020202020202020, p.b + 202020202020202020}); } // 7. 集計. LL ans = 0; rep(i, idx + 1){ // 前回分. LL lBef = v[i][0].a; LL rBef = v[i][0].b; // 各区間の大小関係を比較して, 集計. repx(j, 1, v[i].size()){ // 今回分. LL lCur = v[i][j].a; LL rCur = v[i][j].b; // 区間が連結してない場合. if(rBef < lCur){ ans += (rBef - lBef + D) / D; lBef = lCur; rBef = rCur; continue; } // 区間が連結している場合. rBef = max(rBef, rCur); } } // 8. 出力. 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 |
[入力例] 3 4 2 [出力例] 8 ※AtCoderテストケースより [入力例] 2 3 -3 [出力例] 2 ※AtCoderテストケースより [入力例] 100 14 20 [出力例] 49805 ※AtCoderテストケースより [入力例] 4 3 10 [出力例] 15 [入力例] 7 5 -3 [出力例] 43 [入力例] 314 159 265 [出力例] 246596 [入力例] 2022 -9 15 [出力例] 10210074 [入力例] 2019 1208 -2100 [出力例] 1007787494 [入力例] 1234 567 890 [出力例] 313181180 [入力例] 123456 20202020 30303030 [出力例] 22862137621 |
■参照サイト
AtCoder Beginner Contest 147