C++の練習を兼ねて, AtCoder Regular Contest 073 の 問題E (Ball Coloring) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 073 解説 を ご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://img.atcoder.jp/arc073/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using P = pair<int, int>; using vp = vector<P>; #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() const int INF = 2020202020; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp v; rep(i, N){ // ボールの情報を保存. int x, y; scanf("%d %d", &x, &y); if(x > y) swap(x, y); v.pb({x, y}); } // 2. (Rmax - Rmin) * (Bmax - Bmin) の 最大値は? // 2-1. Rmin = MIN かつ Bmax = MAX の 場合. int rMin = INF, rMax = 0, bMin = INF, bMax = 0; rep(i, v.size()){ rMin = min(rMin, v[i].a); rMax = max(rMax, v[i].a); bMin = min(bMin, v[i].b); bMax = max(bMax, v[i].b); } LL ans1 = (LL)(rMax - rMin) * (LL)(bMax - bMin); // 2-2. Rmin = MIN かつ Rmax = MAX の 場合. // -> 赤色には, 何も考えずに, 好きなボールを割り当てる. rMin = INF, rMax = 0; rep(i, v.size()){ rMin = min(rMin, v[i].a); rMax = max(rMax, v[i].b); } // 各袋について, ボールを交換. int bMinMax = INF; multiset<int> m; sort(all(v)); for(auto &p : v) m.insert(p.a); for(auto &p : v){ // 交換. auto itr1 = m.find(p.a); m.erase(itr1); // 1個だけ削除. m.insert(p.b); // 1個だけ追加. // 最初のボール. auto itr2 = m.begin(); int s = *(itr2); // 最後のボール. auto itr3 = m.end(); int e = *(--itr3); // 差分の最小値更新. bMinMax = min(bMinMax, e - s); } LL ans2 = (LL)(rMax - rMin) * (LL)bMinMax; // 3. 出力. printf("%lld\n", min(ans1, ans2)); 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 |
[入力例] 3 1 2 3 4 5 6 [出力例] 15 ※AtCoderのテストケースより [入力例] 3 1010 10 1000 1 20 1020 [出力例] 380 ※AtCoderのテストケースより [入力例] 2 1 1 1000000000 1000000000 [出力例] 999999998000000001 ※AtCoderのテストケースより [入力例] 10 3 5 7 5 3 6 1 3 11 9 9 3 7 12 5 2 1 6 11 8 [出力例] 66 [入力例] 25 27 17 26 18 11 21 26 31 28 17 10 14 15 22 15 12 10 15 18 21 16 29 25 15 15 23 26 16 31 11 15 24 24 16 19 32 28 14 15 18 33 16 16 10 35 31 26 28 30 27 [出力例] 425 [入力例] 50 229 378 159 183 472 144 391 150 336 219 155 169 263 413 297 335 285 468 222 255 352 183 378 348 369 185 429 452 239 340 253 223 177 406 294 237 130 439 183 234 458 215 377 296 151 233 427 392 352 255 219 228 418 408 326 130 324 184 284 153 215 202 500 362 499 404 211 304 391 161 196 443 257 322 405 144 323 364 435 388 357 143 130 273 437 408 336 364 435 392 190 176 409 223 236 130 334 131 187 296 [出力例] 98969 |
■参照サイト
AtCoder Regular Contest 073