C++の練習を兼ねて, AtCoder Regular Contest 121 の 問題A (2nd Greatest Distance) ～ 問題B (RGB Matching) を解いてみた.
■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 121 解説 の 各リンク を ご覧下さい.
■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 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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; 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 #define a first #define b second #define all(x) x.begin(), x.end() int ox[202020], oy[202020]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp px, py; rep(i, N){ int x, y; scanf("%d %d", &x, &y); // 平行移動. x += 1e9; y += 1e9; // オリジナル座標を保存. ox[i] = x; oy[i] = y; // {x, i} を 保存. px.pb({x, i}); // {y, i} を 保存. py.pb({y, i}); } // 2. sort. sort(all(px)); sort(all(py)); // 3. チェビシェフ距離を保存. // -> hand_01.txt で, WA版となったので修正. vi ans; set<P> st; // インデックスが出現済かのチェック. // 3-1. X成分について, 最大四通り保存. for(auto &i : {N - 1, N - 2}){ for(auto &j : {0, 1}){ if(!st.count({px[i].b, px[j].b}) || !st.count({px[j].b, px[i].b})){ st.insert({px[i].b, px[j].b}); st.insert({px[j].b, px[i].b}); ans.pb(max(px[i].a - px[j].a, abs(oy[px[i].b] - oy[px[j].b]))); } } } // 3-2. Y成分について, 最大四通り保存. for(auto &i : {N - 1, N - 2}){ for(auto &j : {0, 1}){ if(!st.count({py[i].b, py[j].b}) || !st.count({py[j].b, py[i].b})){ st.insert({py[i].b, py[j].b}); st.insert({py[j].b, py[i].b}); ans.pb(max(py[i].a - py[j].a, abs(ox[py[i].b] - ox[py[j].b]))); } } } // 4. sort. sort(all(ans)); reverse(all(ans)); // 5. 出力. printf("%d\n", ans[1]); 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 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 |
[入力例] 3 0 0 1 2 4 0 [出力例] 3 ※AtCoderのテストケースより [入力例] 4 0 0 0 0 1 0 0 1 [出力例] 1 ※AtCoderのテストケースより [入力例] 20 407 361 167 433 756 388 -551 -47 306 -471 36 928 338 -355 911 852 288 70 -961 -769 -668 -386 -690 -378 182 -609 -677 401 -458 -112 184 -131 -243 888 -163 471 -11 997 119 544 [出力例] 1766 ※AtCoderのテストケースより [入力例] 5 222 555 111 222 -222 333 333 -111 -555 -222 [出力例] 777 [入力例] 7 -1 1 -2 2 -3 3 -4 4 -5 5 -6 6 -7 7 [出力例] 5 [入力例] 5 -1 -1 2 2 3 3 4 4 5 5 [出力例] 5 [入力例] 60 72 36 59 93 14 60 31 23 35 43 80 68 70 22 33 90 39 -39 80 -39 40 10 91 25 9 49 99 -11 18 35 -44 -12 3 63 -53 61 98 40 36 -24 45 33 -44 71 38 70 62 79 62 51 -44 20 34 66 79 52 90 74 76 54 30 69 9 42 92 59 75 71 58 -1 7 85 66 46 -53 59 22 43 58 86 22 29 5 -37 43 48 65 50 61 25 11 20 16 21 84 77 43 50 56 82 47 88 40 86 45 74 75 26 31 59 48 48 25 44 24 30 3 12 22 44 [出力例] 152 |
■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 |
// 解き直し. // https://atcoder.jp/contests/arc121/editorial/1927 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 main(){ // 1. 入力情報. int N; scanf("%d", &N); vl r, g, b; rep(i, N * 2){ LL x; char c[11]; scanf("%lld %s", &x, c); if(c[0] == 'R') r.pb(x); if(c[0] == 'G') g.pb(x); if(c[0] == 'B') b.pb(x); } // 2. 出現回数が, すべて偶数だった場合. int lr = r.size(), lg = g.size(), lb = b.size(); bool fr = (lr & 1), fg = (lg & 1), fb = (lb & 1); if(!fr && !fg && !fb){ puts("0"); return 0; } // 3. sort. sort(all(r)); sort(all(g)); sort(all(b)); // 4. 二色間の不満の最小値を計算. // 4-1. (赤, 緑). LL rg = 202020202020202020; rep(i, lr){ int at = lower_bound(all(g), r[i]) - g.begin(); if(at) rg = min(rg, abs(r[i] - g[at - 1])); if(at < lg) rg = min(rg, abs(r[i] - g[at])); } // 4-2. (緑, 青). LL gb = 202020202020202020; rep(i, lg){ int at = lower_bound(all(b), g[i]) - b.begin(); if(at) gb = min(gb, abs(g[i] - b[at - 1])); if(at < lb) gb = min(gb, abs(g[i] - b[at])); } // 4-3. (青, 赤). LL br = 202020202020202020; rep(i, lb){ int at = lower_bound(all(r), b[i]) - r.begin(); if(at) br = min(br, abs(b[i] - r[at - 1])); if(at < lr) br = min(br, abs(b[i] - r[at])); } // 5. 不満の総和(最小値)を計算. LL ans = 0; // 5-1. (R, G, B) = (奇, 奇, 偶). if(fr && fg && !fb) ans = min(rg, gb + br); // 5-2. (R, G, B) = (奇, 偶, 奇). if(fr && !fg && fb) ans = min(br, rg + gb); // 5-3. (R, G, B) = (偶, 奇, 奇). if(!fr && fg && fb) ans = min(gb, br + rg); // 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 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 |
[入力例] 1 1 R 2 G [出力例] 1 ※AtCoderのテストケースより [入力例] 1 1 B 2 B [出力例] 0 ※AtCoderのテストケースより [入力例] 10 585 B 293 B 788 B 222 B 772 G 841 B 115 R 603 G 450 B 325 R 851 B 205 G 134 G 651 R 565 R 548 B 391 G 19 G 808 B 475 B [出力例] 0 ※AtCoderのテストケースより [入力例] 5 98 R 102 R 120 G 7 B 6 G 120 B 109 G 52 G 36 G 86 R [出力例] 7 [入力例] 50 11244743 B 5877149 B 5099161 G 1208388 G 1648015 G 3217963 G 11108936 R 4512846 R 10124520 R 2074767 R 8806995 G 2282762 G 7053673 G 2677487 R 7801965 R 11788960 B 10571032 R 4599279 G 1388012 B 11206734 G 11187751 R 8937750 R 9137969 R 1472865 G 7856676 B 7150864 B 11772619 B 8227625 R 11934812 R 2422385 B 3797610 B 1625819 G 7740320 G 4874554 R 6450228 R 6270440 G 9044072 G 11323991 G 9005953 R 2933852 G 3548266 G 5176481 R 5019226 G 1856370 R 4647775 G 980522 G 180201 R 6965382 R 8372851 G 2160152 R 9430055 B 1001030 G 12327675 R 6563200 R 1863499 G 9586292 G 1434649 R 6703481 R 11164197 G 8360086 G 3664837 B 5710294 G 7038426 R 3582456 G 4453263 B 3958311 B 3182379 B 628331 G 3797981 G 9503947 G 12044492 R 11378209 G 4543606 R 6054089 B 8452268 G 12178767 B 1306080 R 11467141 R 9516770 G 3402052 G 7283144 G 10900531 G 12170455 G 8432463 G 6337490 B 5242718 B 10205154 R 4084846 B 1237260 R 1056401 G 1166758 G 3866554 G 4518124 G 9219884 B 377518 G 2593292 G 7634244 B 11914718 R 9352220 R 5863932 B [出力例] 5278 |
■参照サイト
AtCoder Regular Contest 121