C++の練習を兼ねて, AtCoder Grand Contest 021 の 問題A (Digit Sum 2) ～ 問題B (Holes) を解いてみた.
■感想.
1. 問題A, Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 問題B は, 凸包作成の実装に, 非常に苦労したものの, 個人的には, 面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 021 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/agc021/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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. 入力情報. char c[111]; scanf("%s", c); string N(c); int n = N.size(); // 2. 各桁の和の最大値を計算. // 2-1. c999...999 の パターンであるか判定. bool ok = true; repr(i, n - 1, 1){ if(N[i] != '9'){ ok = false; break; } } // 2-2. 各桁の和を計算. int ans = 9 * (n - 1) + (N[0] - '0'); if(!ok) ans--; // 3. 出力. printf("%d\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 |
[入力例] 100 [出力例] 18 ※AtCoderテストケースより [入力例] 9995 [出力例] 35 ※AtCoderテストケースより [入力例] 3141592653589793 [出力例] 137 ※AtCoderテストケースより [入力例] 2021 [出力例] 28 [入力例] 20210410 [出力例] 64 [入力例] 9999999999999999 [出力例] 144 [入力例] 11939623286980429648566048291655261423757411936705 [出力例] 441 ※1e16よりも大きいケース(問題文の制約条件から外れるケース). |
■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 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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 |
// 解き直し. // https://img.atcoder.jp/agc021/editorial.pdf // 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--) #define all(x) x.begin(), x.end() #define pb push_back const double PI = acos(-1); LL x[111], y[111]; int memo[111]; double ans[111]; struct hole{ LL x, y; // 座標. int i; // 入力番号. bool operator < (const hole& rhs) const{ return (x < rhs.x) || ((x == rhs.x) && (y < rhs.y)); } }; struct edge{ double t; // 基準座標からの回転角. LL d; // 座標間の距離(2乗). LL x, y; // 座標. int i; // 基準座標から見た凸包候補の入力番号. bool operator < (const edge& rhs) const{ return (t < rhs.t) || ((t == rhs.t) && (d > rhs.d)); } }; struct point{ LL x, y; // 座標. }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vector<hole> v; rep(i, N){ hole h; scanf("%lld %lld", &x[i], &y[i]); h.x = x[i]; h.y = y[i]; h.i = i; v.pb(h); } // 2. sort. sort(all(v)); // for(auto &p : v) printf("%lld %lld %d\n", p.x, p.y, p.i); // 3. 凸包の作成. vector<hole> convex; hole o = v[0]; // 開始地点. int idx = o.i; convex.pb(o); point b; // 前回分ベクトル. b.x = o.x, b.y = o.y + 2e6 + 1; while(!memo[idx]){ // 3-1. 訪問済みフラグ設定. memo[idx]++; // 3-2. 起点を取得. hole s = convex.back(); // 3-3. 起点から線分を引いた場合の回転角, 距離 を 保存. vector<edge> candidate; rep(i, N){ hole e = v[i]; if(!memo[e.i]){ edge p; // ベクトル v1, v2 の 内積から, 回転角を算出. double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y); double v2x = (double)(e.x - s.x), v2y = (double)(e.y - s.y); double iProduct = v1x * v2x + v1y * v2y; double normBsSe = hypot(v1x, v1y) * hypot(v2x, v2y); double theta = acos(iProduct / normBsSe); p.t = theta; // 距離. p.d = (e.x - s.x) * (e.x - s.x) + (e.y - s.y) * (e.y - s.y); // 座標. p.x = e.x; p.y = e.y; // 入力番号. p.i = e.i; // 追加. candidate.pb(p); } } // 3-4. 凸包候補 が見つからなかった場合は, 終了. if(!candidate.size()) break; // 3-5. sort. sort(all(candidate)); // 3-6. 凸包に保存してよいかチェック. bool ok = convex.size() > 2; if(ok){ double theta1 = candidate[0].t; // ベクトル v1, v2 の 内積から, 回転角を算出. double v1x = (double)(s.x - b.x), v1y = (double)(s.y - b.y); double v2x = (double)(o.x - s.x), v2y = (double)(o.y - s.y); double iProduct = v1x * v2x + v1y * v2y; double normBsSo = hypot(v1x, v1y) * hypot(v2x, v2y); double theta2 = acos(iProduct / normBsSo); // 凸包内部に移動する場合は, 終了. if(theta2 < theta1) break; } // 3-7. 凸包に保存. hole h; h.i = candidate[0].i; h.x = x[h.i]; h.y = y[h.i]; convex.pb(h); // 3-8. 前回分ベクトル更新. b.x = s.x; b.y = s.y; // 3-9. index更新. idx = h.i; // 3-10. 訪問済みフラグ設定. if(ok){ for(auto &p : candidate){ if(p.i == idx) continue; if(!memo[p.i]){ // ベクトル va, vb が定数倍の差分であるかチェック. // ※ 凸包の辺上にあるかのチェック. LL vax = h.x - s.x, vay = h.y - s.y; LL vbx = p.x - s.x, vby = p.y - s.y; // (vax = 0 and vbx = 0) or (vay = 0 and vby = 0) の 場合. if((vax == 0 && vbx == 0) || (vay == 0 && vby == 0)) memo[p.i]++; // それ以外 の 場合. if(vbx != 0 && vby != 0 && (vax % vbx == 0) && (vay % vby == 0)){ LL kx = vax / vbx, ky = vay / vby; if(kx == ky) memo[p.i]++; } } } } } // 4. 垂直二等分線(pq/qr) の 角度(差分) を 計算・保存. hole s = convex.front(); hole e = convex.back(); convex.pb(s); convex.insert(convex.begin(), e); repx(i, 1, convex.size() - 1){ // 4-1. 穴 p, q, r. hole p = convex[i - 1]; hole q = convex[i]; hole r = convex[i + 1]; // 4-2. ベクトル qr, qp の 内積から, 角度を算出. double qrx = (double)(r.x - q.x), qry = (double)(r.y - q.y); double qpx = (double)(p.x - q.x), qpy = (double)(p.y - q.y); double iProduct = qrx * qpx + qry * qpy; double normQrQp = hypot(qrx, qry) * hypot(qpx, qpy); double theta = acos(iProduct / normQrQp); // 4-3. 垂直二等分線 の 角度(差分). ans[q.i] = PI - theta; // 4-4. 360度で割る. ans[q.i] /= (2.0 * PI); } // 5. 出力. rep(i, N) printf("%.12lf\n", ans[i]); 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 110 111 112 113 114 115 116 |
[入力例] 2 0 0 1 1 [出力例] 0.5 0.5 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 0.499999996646 0.499999996646 [入力例] 5 0 0 2 8 4 5 2 6 3 10 [出力例] 0.43160120892732328768 0.03480224363653196956 0.13880483535586193855 0.00000000000000000000 0.39479171208028279727 ※AtCoderテストケースより ※但し, 上記のプログラムでは, 以下の内容が出力される. 0.431601208927 0.034802243637 0.138804835356 0.000000000000 0.394791712080 [入力例] 10 -23 78 -101 121 6 -9 -95 -64 -103 67 93 -35 97 99 31 29 47 -52 111 -8 [出力例] 0.000000000000 0.261719709303 0.000000000000 0.253710502864 0.015599264789 0.100076037181 0.211681970670 0.000000000000 0.042922608696 0.114289906496 [入力例] 25 -517 7628 8075 -2012 154 -40 -8256 11959 -9146 -6877 7850 3547 -948 -11197 -941 8748 -9147 -7807 10584 9401 -6647 12172 -8579 2928 6496 -93 11613 5783 10229 6921 4040 6678 5758 9469 9099 6744 -1513 10487 -5487 -2871 -1409 -9841 3928 -10419 9571 4500 -7524 -9713 4449 2480 [出力例] 0.000000000000 0.005121649771 0.000000000000 0.221538334289 0.007343339491 0.000000000000 0.060506653058 0.000000000000 0.112435325509 0.180521831195 0.046324389216 0.000000000000 0.000000000000 0.111913140296 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.000000000000 0.151884160566 0.000000000000 0.102411176608 0.000000000000 |
■参照サイト
AtCoder Grand Contest 021