C++の練習を兼ねて, AtCoder Beginner Contest 281 の 問題E (Least Elements) を解いてみた.
■感想.
1. 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 281 解説 の 各リンク を ご覧下さい.
■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 |
// C++(GCC 9.2.1) #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--) LL a[202020]; int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); rep(i, N) scanf("%lld", &a[i]); // 2. 先頭 の (M - 1) 項. multiset<LL> lMst, rMst; rep(i, M - 1){ lMst.insert(a[i]); if(lMst.size() > K){ auto e = (--lMst.end()); rMst.insert(*e); lMst.erase(lMst.find(*e)); } } LL ans = 0; for(auto &x : lMst) ans += x; // 3. クエリ回答. repx(i, M - 1, N){ // 3-1. a[i - M] の 処理. if(i - M >= 0){ if(lMst.find(a[i - M]) != lMst.end()){ ans -= a[i - M]; lMst.erase(lMst.find(a[i - M])); }else{ rMst.erase(rMst.find(a[i - M])); } } // 3-2. a[i] の 処理. rMst.insert(a[i]); if(lMst.size() < K){ auto s = rMst.begin(); ans += *s; lMst.insert(*s); rMst.erase(rMst.find(*s)); }else{ auto s = rMst.begin(); auto e = (--lMst.end()); if(*e > *s){ ans += *s; lMst.insert(*s); rMst.erase(rMst.find(*s)); ans -= *e; rMst.insert(*e); lMst.erase(lMst.find(*e)); } } // 3-3. 出力. printf("%lld%s", ans, (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 |
[入力例] 6 4 3 3 1 4 1 5 9 [出力例] 5 6 10 ※AtCoderテストケースより [入力例] 10 6 3 12 2 17 11 19 8 4 3 6 20 [出力例] 21 14 15 13 13 ※AtCoderテストケースより [入力例] 5 3 3 1 1 1 1 1 [出力例] 3 3 3 [入力例] 7 3 3 1 2 3 2 1 2 3 [出力例] 6 7 6 5 6 [入力例] 10 5 3 1 2 3 4 5 4 3 2 1 2 [出力例] 6 9 10 9 6 5 [入力例] 50 10 7 76 105 111 38 82 122 7 110 61 90 39 111 113 8 109 110 15 117 5 111 110 115 5 13 34 111 111 39 121 73 110 36 111 61 83 116 111 5 110 89 93 111 2 110 62 75 72 5 5 79 [出力例] 459 422 427 427 397 424 424 432 432 376 397 468 468 362 367 292 293 389 317 423 385 385 310 416 464 513 513 513 479 478 494 477 552 443 492 471 436 398 398 310 300 [入力例] 100 12 5 111 222 333 2023 785 147 724 1215 2023 103 712 103 111 270 111 906 196 567 777 809 196 111 621 753 1010 717 761 57 811 570 177 1183 103 555 748 1065 585 999 377 1173 285 624 187 2023 876 287 210 175 792 256 141 1133 59 1225 945 478 729 115 53 286 777 111 2023 103 2023 715 2023 335 111 1 103 1200 65 493 71 604 650 90 103 19 111 111 1123 111 103 1210 1025 110 689 191 750 2023 1124 515 888 1219 200 2023 103 126 [出力例] 686 686 734 575 575 575 624 624 624 624 632 632 725 884 1181 1691 1127 1552 1555 1111 1111 1018 1462 1462 1462 1462 1462 1269 1782 1497 1497 1507 1507 1989 1721 1346 1144 1144 1113 969 969 772 772 841 841 841 700 543 624 624 479 624 441 668 668 668 668 493 379 429 429 383 383 343 351 351 330 330 246 246 348 348 348 386 386 426 425 425 446 454 546 626 1030 1030 1608 1705 1705 1119 1135 |
■参照サイト
AtCoder Beginner Contest 281