C++の練習を兼ねて, AtCoder Beginner Contest 116 の 問題D (Various Sushi) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 優先順位付きキューを活用することで, 解説のロジックが, 実装できることに, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 116 解説 を ご覧下さい.
■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 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
// 解き直し. // https://img.atcoder.jp/abc116/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>; using PQD = priority_queue<P>; using PQA = priority_queue<P, vector<P>, greater<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() int main(){ // 1. 入力情報. int N, K, t, d; scanf("%d %d", &N, &K); vp v; rep(i, N){ scanf("%d %d", &t, &d); v.pb({d, t}); } // 2. sort. sort(all(v)); // 3. 集合 S. LL dSum = 0; map<int, int> m; PQA sIn; repr(i, N - 1, N - K){ sIn.push({v[i].a, v[i].b}); m[v[i].b]++; dSum += (LL)v[i].a; } // 4. 集合 S 以外. PQD sOut; rep(i, N - K) sOut.push({v[i].a, v[i].b}); // 5. 寿司の入れ替え. LL ans = dSum + (LL)m.size() * (LL)m.size(); while(!sIn.empty()){ // 集合 S から, 取り出す. P x = sIn.top(); sIn.pop(); // ネタ の 種類数 が, 減る場合は, Skip. if(m[x.b] == 1) continue; // ネタ の 種類数 が, 変わらない場合は, おいしさ基礎ポイント, ネタの個数 を 更新. dSum -= x.a; m[x.b]--; // 集合 S 以外 を見る. while(!sOut.empty()){ // 集合 S 以外 から 取り出す. P y = sOut.top(); sOut.pop(); // 集合 S に 含まれない ネタ を探す. if(!m.count(y.b)){ // おいしさ基礎ポイント, ネタの個数 を 更新. dSum += y.a; m[y.b]++; // 満足度更新. ans = max(ans, dSum + (LL)m.size() * (LL)m.size()); // 集合 S に 追加. sIn.push({y.a, y.b}); // 次へ. break; } } } // 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 |
[入力例] 5 3 1 9 1 7 2 6 2 5 3 1 [出力例] 26 ※AtCoderテストケースより [入力例] 7 4 1 1 2 1 3 1 4 6 4 5 4 5 4 5 [出力例] 25 ※AtCoderテストケースより [入力例] 6 5 5 1000000000 2 990000000 3 980000000 6 970000000 6 960000000 4 950000000 [出力例] 4900000016 ※AtCoderテストケースより [入力例] 12 5 1 2 2 5 1 7 1 5 7 10 7 3 5 10 4 4 1 6 2 9 5 8 4 9 [出力例] 70 [入力例] 20 7 8 764 5 313 10 861 6 544 8 1262 5 182 7 1202 3 130 5 850 3 981 5 590 10 771 6 50 4 1255 3 552 10 631 3 848 6 659 4 1091 6 1089 [出力例] 7777 [入力例] 50 10 11 6619934 5 1624101 12 5451794 3 9857183 5 1985828 11 11345963 2 5757194 3 6881103 9 1920811 14 8507495 14 5235040 10 4128252 15 1491606 11 768521 12 9822790 13 10069095 7 7116817 12 6611197 4 1247639 2 36843 9 10277716 3 19857 2 11561672 15 631937 5 7841766 13 2487890 13 13479705 8 1159151 2 12291992 7 2711313 7 1707463 10 985172 10 9394217 9 1626609 6 8081696 12 10331209 7 11885741 12 12131871 8 4794885 6 11949323 14 43035 10 9376463 3 12689389 12 7496508 3 8502162 14 4333674 10 15789860 6 9809565 9 7026972 5 1091517 [出力例] 123456789 |
■参照サイト
AtCoder Beginner Contest 116