C++の練習を兼ねて, AtCoder Beginner Contest 197 の 問題C (ORXOR) ～ 問題D (Opposite) を解いてみた.
■感想.
1. 実装に苦労したものの, 解説見る前に, AC版に到達出来たので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Beginner Contest 197 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; #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 LL a[22]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%lld", &a[i]); // 2. 2 の 冪乗 を 保存. vi cPow2; int count = 0; cPow2.pb(1); while(count < N){ // 最大値を2倍. int p = 2 * cPow2.back(); // 保存. cPow2.pb(p); // インクリメント. count++; } // 3. 区間を生成し, 最小値を探索. LL ans = 202020202020202020; rep(i, 1 << N){ // 3-1. 区間を生成. int bef = -1, cur; vi v; rep(j, N){ // 今回分更新. cur = (cPow2[N - 1 - j] & i) ? 1 : 0; // 前回と異なる場合は, 区間開始地点と見て保存. if(bef != cur) v.pb(j); // 前回分更新. bef = cur; } // 3-2. 番兵. v.pb(N); // 3-3. XOR生成. LL cXOR = 0; rep(j, v.size() - 1){ // 区間開始地点, 区間終了地点. LL cOR = 0; int s = v[j]; int e = v[j + 1]; // 区間内の数のビット単位OR を計算. repx(k, s, e) cOR |= a[k]; // 全ての値のビット単位XOR を計算. cXOR ^= cOR; } // 3-4. 最小値更新. ans = min(ans, cXOR); } // 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 |
[入力例] 3 1 5 7 [出力例] 2 ※AtCoderテストケースより [入力例] 3 10 10 10 [出力例] 0 ※AtCoderテストケースより [入力例] 4 1 3 3 1 [出力例] 0 ※AtCoderテストケースより [入力例] 5 1 3 12 18 7 [出力例] 24 [入力例] 10 1 2 3 16 17 31 63 1 2 3 [出力例] 32 [入力例] 18 1 2 2 3 4 5 8 9 16 17 32 33 64 65 128 129 256 257 [出力例] 1 |
■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 |
// 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--) const double PI = acos(-1.0); int main(){ // 1. 入力情報. int N; scanf("%d", &N); double xs, ys, xo, yo; scanf("%lf %lf %lf %lf", &xs, &ys, &xo, &yo); // 2. x1, y1 を 計算. // -> 中心を, C(cx, cy)と置いて, ベクトル P[0]C(ux, uy), P[0]P[1](vx, vy) の関係を確認. double ux = (xs + xo) / 2.0 - xs; double uy = (ys + yo) / 2.0 - ys; double theta = PI * (1.0 - 0.5 - 1.0 / (double)N); double e = 2.0 * cos(theta); double vx = (cos(-theta) * ux - sin(-theta) * uy) * e; double vy = (sin(-theta) * ux + cos(-theta) * uy) * e; double x1 = xs + vx; double y1 = ys + vy; // 3. 出力. printf("%.11lf %.11lf\n", x1, y1); 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 |
[入力例] 4 1 1 2 2 [出力例] 2.00000000000 1.00000000000 ※AtCoderテストケースより [入力例] 6 5 3 7 4 [出力例] 5.93301270189 2.38397459622 ※AtCoderテストケースより [入力例] 8 3 7 19 25 [出力例] 11.70710678119 3.97918471983 [入力例] 30 2 6 75 51 [出力例] 7.47562561662 -1.09709773136 |