C++の練習を兼ねて, AtCoder Beginner Contest 033 の 問題C (C – 数式の書き換え) ～ 問題D (D – 三角形の分類) を解いてみた.
■感想.
1. 問題C は, 個人的には, 非常に面白いと感じる問題だった.
2. 問題D は 方針が見えず, 解説を参照したものの, 実装に大変苦労した(※90度判定を, 2通りの実装で確認した).
※ 苦労した主な内容は,
・直角三角形が, 何故か正しくカウントされない件(※小数点以下の端数処理の考慮)
・int型 → long long型 への型変換忘れによるWA判定(※テストケース 02-13.txt ～ 02-handmade05.txt と 推定)
の二点 で 躓いていたことが判明した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 033解説をご覧下さい.
■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 |
#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--) #define pb push_back int main(){ // 1. 入力情報. char c[101010]; scanf("%s", c); string S(c); // 2. 数式を確認. // 2-1. 先頭(0) を チェック. int l = S.size(); vector<int> v; int a = (S[0] != '0') ? 1 : 0; v.pb(a); // 2-2. それ以外(1 ～ l - 1) を チェック. repex(i, 2, l, 2){ // 左の符号が, '+'. if(S[i - 1] == '+'){ int a = (S[i] != '0') ? 1 : 0; v.pb(a); } // 左の符号が, '*'. if(S[i - 1] == '*'){ int a = (S[i] != '0') ? 1 : 0; int vl = v.size() - 1; v[vl] *= a; } } // 3. 式の値を 0 にするために, '0' に 書き換える個数は？ int ans = 0; for(auto &p : v) ans += p; // 4. 出力. 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 46 47 48 49 50 51 52 53 54 55 56 |
[入力例] 0+0+2*0 [出力例] 0 ※AtCoderテストケースより [入力例] 3*1+1*2 [出力例] 2 ※AtCoderテストケースより [入力例] 3*1*4+0+2*0+5*2+9*8*6+1+3 [出力例] 5 ※AtCoderテストケースより [入力例] 0 [出力例] 0 [入力例] 1 [出力例] 1 [入力例] 1*2*3 [出力例] 1 [入力例] 1*2*3+4 [出力例] 2 [入力例] 3*0*4+0+9+2*1+5*2*9*0*4*9+3*8*6+2*1+0 [出力例] 4 [入力例] 1*2*3+4+5+6+7*8+9*0*9*0*9*8+7*6*5+4*3+2+1+0+1 [出力例] 10 |
■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 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 |
// 解き直し. // AtCoder Beginner Contest 033 解説. // https://www.slideshare.net/chokudai/abc033 #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 pb push_back #define all(x) x.begin(), x.end() double x[2020], y[2020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ double a, b; scanf("%lf %lf", &a, &b); x[i] = a; y[i] = b; } // 2. ベクトルの角度を計算(解説通り). LL o = 0, r = 0; rep(i, N){ // 2-1. 点B を 固定. vector<double> bx, by, angle; rep(j, N){ if(j == i) continue; bx.pb(x[j] - x[i]); by.pb(y[j] - y[i]); } // 2-2. 角度(1周分) を 保存. double pi = acos(-1), pi2 = acos(0); rep(j, bx.size()){ // atan2 は, [-pi, pi] で 返却されることに注意. double a = atan2(by[j], bx[j]); if(a < 0.0) a += pi * 2.0; angle.pb(a); } // 2-3. 角度 を sort. sort(all(angle)); // 2-4. 角度(2周分) に 水増し. int l = angle.size(); rep(j, l) angle.pb(angle[j] + pi * 2.0); // for(auto &p : angle) printf("%lf ", p); // puts(""); // 2-5. 鈍角, 直角 を 数える. int at90 = 0, at180 = 0; rep(j, l){ double a = angle[j]; // 90度を見つける. repx(k, at90, 2 * l){ double b = angle[k]; // ex. // [入力例] // 8 // 0 0 // -2 3 // 0 3 // 1 7 // 2 2 // 3 1 // 2 0 // 3 -1 // // [出力例] // 9 8 39 // // ※上記のテストケースで, 直角三角形 (3, 1), (0, 0), (1, 7) が カウントされなかったので修正. // if(b - a >= pi2){ if(b - a >= pi2 - 1e-12){ at90 = k; // if(b - a == pi2) r++, at90++; if(abs(b - a - pi2) < 1e-12) r++, at90++; break; } } // 180度を見つける. at180 = max(at90, at180); repx(k, at180, 2 * l){ double b = angle[k]; if(b - a >= pi){ at180 = k; o += (LL)(at180 - at90); break; } } } } // 4. 鋭角三角形 を 数える(解説通り). LL n = (LL)N; // 02-13.txt ～ 02-handmade05.txt の WA回避. LL s = n * (n - 1) * (n - 2) / 6; s -= o; s -= r; // 5. 出力. printf("%lld %lld %lld\n", s, r, o); return 0; } |
■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 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 |
// 解き直し. // AtCoder Beginner Contest 033 解説. // https://www.slideshare.net/chokudai/abc033 #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 pb push_back #define all(x) x.begin(), x.end() int x[2020], y[2020]; struct rotation{ int x, y; double a; bool operator < (const rotation& rhs) const{ return a < rhs.a; } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ int a, b; scanf("%d %d", &a, &b); x[i] = a; y[i] = b; } // 2. ベクトルの角度を計算(解説通り). LL o = 0, r = 0; rep(i, N){ // 2-1. 点B を 固定. vector<int> bx, by; rep(j, N){ if(j == i) continue; bx.pb(x[j] - x[i]); by.pb(y[j] - y[i]); } // 2-2. 角度(1周分) を 保存. vector<rotation> angle; double pi = acos(-1), pi2 = acos(0); rep(j, bx.size()){ // atan2 は, [-pi, pi] で 返却されることに注意. double a = atan2(by[j], bx[j]); if(a < 0.0) a += pi * 2.0; rotation r; r.x = bx[j]; r.y = by[j]; r.a = a; angle.pb(r); } // 2-3. 角度 を sort. sort(all(angle)); // 2-4. 角度(2周分) に 水増し. int l = angle.size(); rep(j, l){ rotation r; r.x = angle[j].x; r.y = angle[j].y; r.a = angle[j].a + pi * 2.0; angle.pb(r); } // for(auto &p : angle) printf("%d %d %lf\n", p.x, p.y, p.a); // 2-5. 鈍角, 直角 を 数える. int at90 = 0, at180 = 0; rep(j, l){ int px = angle[j].x; int py = angle[j].y; double pa = angle[j].a; // 90度を見つける. repx(k, at90, 2 * l){ int qx = angle[k].x; int qy = angle[k].y; double qa = angle[k].a; int pq = px * qx + py * qy; // if(qa - pa >= pi2){ if(qa - pa >= pi2 - 1e-6){ at90 = k; if(abs(qa - pa - pi2) < 1e-6 && pq == 0){ r++; at90++; } if(qa - pa > pi2) break; } } // 180度を見つける. at180 = max(at90, at180); repx(k, at180, 2 * l){ double qa = angle[k].a; if(qa - pa > pi){ at180 = k; o += (LL)(at180 - at90); break; } } } } // 4. 鋭角三角形 を 数える(解説通り). LL n = (LL)N; // 02-13.txt ～ 02-handmade05.txt の WA回避. LL s = n * (n - 1) * (n - 2) / 6; s -= o; s -= r; // 5. 出力. printf("%lld %lld %lld\n", s, r, o); 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 |
[入力例] 5 1 3 2 2 3 2 4 1 4 3 [出力例] 1 2 7 ※AtCoderテストケースより [入力例] 9 2 0 1 1 3 1 1 2 5 2 0 3 4 3 2 4 4 4 [出力例] 27 14 43 ※AtCoderテストケースより [入力例] 6 0 0 1 1 1 -1 2 0 0 3 3 -2 [出力例] 2 5 13 [入力例] 5 0 0 0 1 1 3 2 1 2 -1 [出力例] 2 3 5 [入力例] 5 0 0 13 1 -1 13 2 2 4 5 [出力例] 0 1 9 [入力例] 8 0 0 -2 3 0 3 1 7 2 2 3 1 2 0 3 -1 [出力例] 9 8 39 [補足(90度の判定)] ・ケース① ※直角三角形 (0, 0), (0, 3), (2, 0) i=0 j=2 dx=0.000000 dy=3.000000 i=0 j=6 dx=2.000000 dy=0.000000 ・ケース② ※直角三角形 (-2, 3), (1, 7), (2, 0) i=1 j=3 dx=3.000000 dy=4.000000 i=1 j=6 dx=4.000000 dy=-3.000000 ・ケース③ ※直角三角形 (0, 3), (0, 0), (-2, 3) i=2 j=0 dx=0.000000 dy=-3.000000 i=2 j=1 dx=-2.000000 dy=0.000000 ・ケース④ ※直角三角形 (2, 2), (0, 0), (3, 1) i=4 j=0 dx=-2.000000 dy=-2.000000 i=4 j=5 dx=1.000000 dy=-1.000000 ・ケース⑤ ※直角三角形 (3, 1), (0, 0), (1, 7) -> 取りこぼしていることが判明したので, 小数点以下の端数処理の考慮. i=5 j=0 dx=-3.000000 dy=-1.000000 i=5 j=3 dx=-2.000000 dy=6.000000 ・ケース⑥ ※直角三角形 (3, 1), (2, 2), (2, 0) i=5 j=4 dx=-1.000000 dy=1.000000 i=5 j=6 dx=-1.000000 dy=-1.000000 ・ケース⑦ ※直角三角形 (2, 0), (0, 0), (2, 2) i=6 j=0 dx=-2.000000 dy=0.000000 i=6 j=4 dx=0.000000 dy=2.000000 ・ケース⑧ ※直角三角形 (2, 0), (3, 1), (3, -1) i=6 j=5 dx=1.000000 dy=1.000000 i=6 j=7 dx=1.000000 dy=-1.000000 |
■参照サイト
AtCoder Beginner Contest 033