C++の練習を兼ねて, AtCoder Regular Contest 134 の 問題D (Concatenate Subsequences) を解いてみた.
■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 辞書順最小の数列を抽出できることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 134 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/arc134/editorial/3325 // C++ (GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vi = vector<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 a[101010], b[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); // 2. N 項までの 最小値 X. int aMin = INF; rep(i, N) aMin = min(aMin, a[i]); // 3. A[i] = X, A[i] >= B[i]. int bMin = INF; rep(i, N) if(a[i] == aMin && a[i] >= b[i]) bMin = min(bMin, b[i]); if(bMin != INF){ printf("%d %d\n", aMin, bMin); return 0; } // 4. A[i] = X, A[i] < B[i]. // 4-1. A[i] = X となる i. vi y; rep(i, N) if(a[i] == aMin) y.pb(i); // 4-2. A[j] < B[y1]. vp v; int y1 = y.front(); int yk = y.back(); repx(j, yk + 1, N) if(a[j] <= b[y1]) v.pb({a[j], j}); sort(all(v)); for(auto &p : v) if(p.a < b[y1] && p.b > y.back()) y.pb(p.b); // 4-3. A[j] = B[y1]. int n = y.size(); if(n > 1){ // 可能な限り選ぶ. int y2 = y[1]; if(b[y1] < b[y2]){ for(auto &p : v) if(p.a == b[y1] && p.b > y.back()) y.pb(p.b); } } // 5. 出力. // 出力サイズ更新を追加(random_04.txt, random_21.txt, random_24.txt, random_26.txt で, WA版の理由). n = y.size(); rep(i, n) printf("%d ", a[y[i]]); rep(i, n) printf("%d%s", b[y[i]], (i < n - 1) ? " " : "\n"); 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 |
[入力例] 3 2 1 3 1 2 2 [出力例] 1 2 ※AtCoderのテストケースより [入力例] 10 38 38 80 62 62 67 38 78 74 52 53 77 59 83 74 63 80 61 68 55 [出力例] 38 38 38 52 53 77 80 55 ※AtCoderのテストケースより [入力例] 12 52 73 49 63 55 74 35 68 22 22 74 50 71 60 52 62 65 54 70 59 65 54 60 52 [出力例] 22 22 50 65 54 52 ※AtCoderのテストケースより [入力例] 1 2 1 [出力例] 2 1 [入力例] 10 54 42 63 22 59 2 17 63 53 109 14 100 121 62 18 99 65 95 76 38 [出力例] 2 17 53 99 65 76 [入力例] 25 170 488 473 440 56 144 307 493 115 523 64 166 395 361 179 158 117 144 448 568 370 589 480 343 280 284 129 122 203 447 141 470 145 80 386 479 410 316 443 79 316 352 252 114 363 214 335 155 299 532 [出力例] 56 64 117 144 280 447 479 352 252 532 [入力例] 50 169 411 250 134 329 175 517 466 131 547 266 274 579 286 399 206 78 128 604 516 205 305 562 457 467 71 330 336 202 57 78 523 163 362 122 151 394 521 225 514 50 359 452 522 513 266 478 170 138 560 365 232 346 65 164 110 459 555 179 364 375 391 262 277 410 398 273 496 338 465 545 164 583 490 205 597 478 208 67 128 444 413 390 558 376 305 86 319 108 183 588 269 156 108 395 434 98 476 586 325 [出力例] 50 138 560 588 586 325 |
■参照サイト
AtCoder Regular Contest 134