C++の練習を兼ねて, AtCoder Beginner Contest 170 の 問題E (Smart Infants) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に実装したところ, AC版となった.
2. なじみの薄い multiset の 訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 170 解説をご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/abc170/editorial.pdf #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 LL A[202020]; int B[202020]; multiset<LL> rate[202020]; // それぞれの幼稚園に所属する幼児のレートの集合. multiset<LL> maxRate; // それぞれの幼稚園の最強園児のレートの集合. int main(){ // 1. 入力情報. int N, Q; scanf("%d %d", &N, &Q); repx(i, 1, N + 1) scanf("%lld %d", &A[i], &B[i]); // 2. 事前準備(以下, 解説通り). repx(i, 1, N + 1) rate[B[i]].insert(A[i]); repx(i, 1, 202020){ if(rate[i].size() > 0){ auto itr = rate[i].end(); maxRate.insert(*(--itr)); } } // 3. クエリ回答. int C, D; rep(i, Q){ // 3-1. 転園情報. scanf("%d %d", &C, &D); int at = B[C]; // 転園元幼稚園. // 3-2. maxRate から 転園元幼稚園の最強園児のレートを削除. auto it1 = rate[at].end(); auto it2 = maxRate.find(*(--it1)); maxRate.erase(it2); // 1個だけ削除. // 3-3. 転園元幼稚園から転園する園児のレートを削除. auto it3 = rate[at].find(A[C]); rate[at].erase(it3); // 1個だけ削除. // 3-4. maxRate に 転園元幼稚園の最強園児のレートを追加. if(rate[at].size() > 0){ auto it4 = rate[at].end(); maxRate.insert(*(--it4)); } // 3-5. maxRate から 転園先幼稚園の最強園児のレートを削除. if(rate[D].size() > 0){ auto it5 = rate[D].end(); auto it6 = maxRate.find(*(--it5)); maxRate.erase(it6); // 1個だけ削除. } // 3-6. 転園先幼稚園に, 転園する園児のレートを追加. rate[D].insert(A[C]); // 3-7. maxRate に 転園先幼稚園の最強園児のレートを追加. auto it7 = rate[D].end(); maxRate.insert(*(--it7)); // 3-8. 転園する園児の所属する幼稚園の番号を更新. B[C] = D; // 3-9. 出力. auto it8 = maxRate.begin(); LL ans = *it8; 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 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 |
[入力例] 6 3 8 1 6 2 9 3 1 1 2 2 1 3 4 3 2 1 1 2 [出力例] 6 2 6 ※AtCoderテストケースより [入力例] 2 2 4208 1234 3056 5678 1 2020 2 2020 [出力例] 3056 4208 ※AtCoderテストケースより [入力例] 20 25 48039234 1 106894727 3 54034116 4 29384308 1 25419214 1 41960290 2 113411995 1 105430452 5 101633542 2 63004981 3 15337594 4 10494255 3 113037996 2 31400866 1 38043117 4 64839068 4 80433133 4 106837808 5 101886442 5 48230109 2 1 3 4 2 9 3 15 3 19 3 2 1 9 1 12 4 17 3 17 1 18 1 20 5 10 5 7 5 4 1 16 1 20 3 3 1 5 5 8 2 11 1 13 5 14 3 6 5 1 5 [出力例] 80433133 80433133 80433133 80433133 80433133 80433133 80433133 80433133 64839068 64839068 64839068 64839068 64839068 64839068 64839068 54034116 54034116 15337594 15337594 15337594 10494255 10494255 10494255 10494255 10494255 |
■参照サイト
AtCoder Beginner Contest 170