C++の練習を兼ねて, AtCoder Beginner Contest 191 の 問題D (Circle Lattice Points) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に, 大変苦労し, 個人的には, トラップ(小数点, 負数排除, 平行移動, XY座標の大小比較など)が, 非常に多いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 191 解説 の 各リンク を ご覧下さい.
■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 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 |
// 解き直し. // https://atcoder.jp/contests/abc191/editorial/611 // 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--) const int D = 10000; int main(){ // 1. 入力情報. double x, y, r; scanf("%lf %lf %lf", &x, &y, &r); // 2. 10000倍 かつ 平行移動(負数 の パターン を 無くし, random_09.txt などの WA を 回避するため). LL X = D * x + 1e10; LL Y = D * y + 1e10; LL R = D * r; // 3. swap(handmade_marginal_00.txt などの WA を 回避するため). if(X > Y) swap(X, Y); // 4. x の 最小値, 最大値(但し, 10000 の 倍数). LL xMin = X - R; LL xMax = X + R; LL qMinX = xMin / D; LL qMaxX = xMax / D; while(qMinX * D < xMin) ++qMinX; while(qMaxX * D > xMax) --qMaxX; // 5. 格子点をカウントする. LL ans = 0; repx(i, (int)qMinX, (int)(qMaxX + 1)){ // x方向. LL curX = (LL)i * (LL)D; // y方向. // -> handmade_marginal_01.txt などの WA を 回避するため, 1 加算. LL dy = (LL)sqrt(R * R - (curX - X) * (curX - X)) + 1; LL yMin = Y - dy; LL yMax = Y + dy; // y の 最小値, 最大値(但し, 10000 の 倍数). // -> qMinY * D < yMin, qMaxY * D > yMax は, 判定条件として甘いことが分かったため, 廃止. LL qMinY = yMin / D; LL qMaxY = yMax / D; LL dx = R * R - (curX - X) * (curX - X); while((qMinY * D - Y) * (qMinY * D - Y) > dx) ++qMinY; while((qMaxY * D - Y) * (qMaxY * D - Y) > dx) --qMaxY; // 集計. ans += (qMaxY - qMinY + 1); } // 6. 出力. 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 |
[入力例] 0.2 0.8 1.1 [出力例] 3 ※AtCoderテストケースより [入力例] 100 100 1 [出力例] 5 ※AtCoderテストケースより [入力例] 42782.4720 31949.0192 99999.99 [出力例] 31415920098 ※AtCoderテストケースより [入力例] 12 13 14 [出力例] 613 [入力例] 12.3 23.4 34.5 [出力例] 3737 [入力例] 12345.6789 98765.4321 10101.0101 [出力例] 320538029 [入力例] 55555.5555 66666.6666 77777.7777 [出力例] 19004696639 |
■参照サイト
AtCoder Beginner Contest 191