C++の練習を兼ねて, AtCoder Regular Contest 123 の 問題E (Training) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 場合分けが多く, 実装に苦労したものの, 解説のロジックで, 個数を高速に数え上げることが出来る点に, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 123 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/arc123/editorial/2291 // 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. Σ[A + x / B]. auto o = [&](LL N, LL a, LL b) -> LL { // ex. // N = 16, B = 3 の 時, Σ[x / B] の 値は？ // 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 // 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5 // -> 0 ～ 5 は, B個(3個)ずつあるので, (初項 0 + 最終項 5) * 6個 / 2 * B個 = 45 // 5 は, 2個余分なので, 5 * (B - N % B) = 5 * 2 = 10 // 計算結果は, 45 - 10 = 35 となる. // // 2-1. 区間[0, N) での総和. LL q = N / b; LL r = N % b; LL ret = 0; // A は N項. ret += a * N; // B個ずつ出現. ret += q * (q + 1) / 2 * b; // 超過分. ret -= q * (b - r); // 2-2. 計算結果. return ret; }; // 3. テストケース. rep(i, T){ // 3-1. 各テストケース. LL N, ax, bx, ay, by; scanf("%lld %lld %lld %lld %lld", &N, &ax, &bx, &ay, &by); // 3-2. 例外(bx = by). if(bx == by){ printf("%lld\n", (ax != ay) ? 0LL : N); continue; } // 3-3. 例外. if((ax > ay && by >= bx) || (ax < ay && by <= bx)){ puts("0"); continue; } // 3-4. 例外(ax = ay). // -> m / bx <= m / by + 1 となる最大の m は？ if(ax == ay){ if(bx > by) swap(bx, by); LL n = min(by * bx / (by - bx), N + 1); LL f = o(n, ax, bx); LL g = o(n, ay, by); printf("%lld\n", n - 1 - abs(f - g)); continue; } // 3-5. swap. if(ax < ay){ swap(ax, ay); swap(bx, by); } // 3-6. 大小が入れ替わる地点. // パターン① (ax + m / bx = ay + m / by). LL m = (ax - ay) * bx * by / (bx - by); m = min(max(0LL, m), N); // パターン② (ax + m / bx <= ay + m / by + 1). LL l = (ax - ay - 1) * bx * by / (bx - by); l = min({max(0LL, l), m, N}); // パターン③ (ax + m / bx + 1 >= ay + m / by). LL r = (ax - ay + 1) * bx * by / (bx - by); r = min(max({0LL, m, r}), N); // 3-7. 区間[l, m). LL fl = o(m, ax, bx) - o(l, ax, bx); LL gl = o(m, ay, by) - o(l, ay, by); // 3-8. 区間[m, r + 1). LL fr = o(r + 1, ax, bx) - o(m, ax, bx); LL gr = o(r + 1, ay, by) - o(m, ay, by); // 3-9. 出力. if(l >= N) puts("0"); else printf("%lld\n", r - l + 1 - abs(fl - gl) - abs(fr - gr)); } 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 |
[入力例] 5 10 5 3 4 2 5 5 3 4 2 100 5 3 4 2 10 5 3 4 3 10 5 10 5 9 [出力例] 6 3 6 0 9 ※AtCoderテストケースより [入力例] 10 1060 17 1 69 8 644 76 7 59 5 330 122 8 117 5 542 31 3 61 6 753 48 3 82 10 262 50 11 49 10 561 103 9 112 11 1045 106 7 109 12 861 50 8 49 7 889 77 12 80 15 [出力例] 1 17 13 6 3 110 49 17 56 60 [入力例] 15 354 101 25 110 120 545 110 17 112 23 292 35 83 33 78 576 53 10 48 7 945 99 96 97 90 291 111 79 110 77 337 77 86 78 88 270 115 32 116 36 326 26 93 59 2 242 4 27 91 78 315 55 23 59 97 244 110 5 111 7 512 34 35 36 40 302 68 9 70 13 324 46 117 44 2 [出力例] 25 65 0 23 0 12 12 127 0 0 28 17 98 29 2 |
■参照サイト
AtCoder Regular Contest 123