C++の練習を兼ねて, AtCoder Beginner Contest 306 の 問題C (Centers) ～ 問題E (Best Performances) を解いてみた.
■感想.
1. 問題C ～ 問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法 の訓練が積めたので, 非常に良かったと思う.
3. 問題Eで, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 306 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; 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 all(x) x.begin(), x.end() #define a first #define b second int a[303030], c[101010]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N * 3) scanf("%d", &a[i]); // 2. f[i]. vp f; rep(i, N * 3) if(++c[a[i]] == 2) f.pb({i, a[i]}); // 3. sort. sort(all(f)); // 4. 出力. rep(i, N) printf("%d%s", f[i].b, (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 |
[入力例] 3 1 1 3 2 3 2 2 3 1 [出力例] 1 3 2 ※AtCoderテストケースより [入力例] 1 1 1 1 [出力例] 1 ※AtCoderテストケースより [入力例] 4 2 3 4 3 4 1 3 1 1 4 2 2 [出力例] 3 4 1 2 ※AtCoderテストケースより [入力例] 5 5 1 5 1 2 2 3 4 1 3 4 4 5 3 2 [出力例] 5 1 2 3 4 [入力例] 10 7 8 9 10 5 6 7 10 1 2 10 9 1 2 3 4 5 6 3 4 4 5 1 2 8 9 6 7 8 3 [出力例] 7 10 9 1 2 5 6 3 4 8 |
■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 |
// 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--) int x[303030], y[303030]; LL dp[303030][2]; // (第二成分) 0: お腹を壊してない, 1: お腹を壊している. int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d %d", &x[i], &y[i]); // 2. dp更新. repx(i, 1, N + 1){ // 前回分. dp[i][0] = dp[i - 1][0]; dp[i][1] = dp[i - 1][1]; // 解毒剤入りの料理. if(x[i - 1] == 0){ // 下げてもらう, お腹を壊していない時, お腹を壊している時. dp[i][0] = max({dp[i][0], dp[i - 1][0] + y[i - 1], dp[i - 1][1] + y[i - 1]}); } // 毒入りの料理. if(x[i - 1] == 1){ // 下げてもらう, お腹を壊していない時. dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i - 1]); } } // 3. 出力. printf("%lld\n", max(dp[N][0], dp[N][1])); 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 |
[入力例] 5 1 100 1 300 0 -200 1 500 1 300 [出力例] 600 ※AtCoderテストケースより [入力例] 4 0 -1 1 -2 0 -3 1 -4 [出力例] 0 ※AtCoderテストケースより [入力例] 15 1 900000000 0 600000000 1 -300000000 0 -700000000 1 200000000 1 300000000 0 -600000000 1 -900000000 1 600000000 1 -100000000 1 -400000000 0 900000000 0 200000000 1 -500000000 1 900000000 [出力例] 4100000000 ※AtCoderテストケースより [入力例] 5 0 -47 1 37 1 47 0 -1 1 31 [出力例] 77 [入力例] 17 1 -5927 0 -5083 1 -4874 0 2133 0 -3008 1 -4097 0 -6399 1 -7708 0 5110 1 3952 1 -8882 0 415 1 2652 0 -8000 1 6377 1 2607 0 2013 [出力例] 20000 [入力例] 50 1 443328 0 73836 1 935506 0 167707 1 -721984 1 868820 1 935436 1 -837258 0 -178397 1 466026 0 256747 1 598834 0 -346502 1 245871 1 -448547 1 -840209 1 -322995 0 858559 1 953866 1 -601510 1 402645 0 737038 0 -305937 0 617873 0 370498 1 -526848 1 434673 0 784215 1 860840 1 73853 1 299615 1 777998 0 -811686 0 -532055 1 -347241 0 181457 0 -180547 1 -156049 1 -701547 0 198698 1 423549 1 -408934 1 -584618 0 19276 1 226669 0 -728976 1 690256 0 297078 1 873101 1 530457 [出力例] 12000000 |
■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 81 82 83 84 85 86 87 88 |
// 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[505050]; int main(){ // 1. 入力情報. int N, K, Q; scanf("%d %d %d", &N, &K, &Q); // 2. 事前準備. multiset<LL> lMst, rMst; rep(i, N){ if(i < N - K) lMst.insert(0); else rMst.insert(0); } // 3. クエリ回答. LL f = 0; rep(i, Q){ // クエリ入力情報. int x, y; scanf("%d %d", &x, &y); --x; // 更新予定の値. LL cur = a[x]; // 更新. a[x] = y; // 左側. bool isSwap = false; if(!lMst.empty()){ auto lItr = lMst.find(cur); if(lItr != lMst.end()){ // 入れ替え. lMst.erase(lItr); lMst.insert(y); isSwap = !isSwap; } } // 右側. auto rItr = rMst.find(cur); if(!isSwap && rItr != rMst.end()){ // 入れ替え. rMst.erase(rItr); rMst.insert(y); // f 更新. f += y; f -= cur; } // 最大値チェック. if(!lMst.empty()){ LL lMax = *(--lMst.end()); LL rMin = *rMst.begin(); if(lMax > rMin){ // 削除. auto lDel = lMst.find(lMax); lMst.erase(lDel); auto rDel = rMst.find(rMin); rMst.erase(rDel); // 追加. lMst.insert(rMin); rMst.insert(lMax); // f 更新. f += lMax; f -= rMin; } } // 出力. printf("%lld\n", f); } 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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 |
[入力例] 4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0 [出力例] 5 6 8 8 15 13 13 11 1 0 ※AtCoderテストケースより [入力例] 10 3 30 2 120 7 114 1 36 9 99 1 8 7 122 2 45 1 58 6 88 9 74 7 69 2 6 3 10 5 31 3 116 3 73 9 32 2 43 7 38 7 41 9 61 4 14 6 28 4 110 8 10 6 91 7 100 1 53 5 112 6 79 [出力例] 120 234 270 333 333 341 266 279 309 284 231 231 231 231 278 235 230 230 219 219 222 222 192 244 244 274 301 301 322 322 [入力例] 20 5 100 6 8520 9 1903 7 10099 2 655 8 9326 16 2653 19 6018 13 4188 7 4612 7 5699 18 7730 5 383 12 3149 6 764 7 3043 7 1626 8 2701 17 9019 1 2749 17 8514 18 89 4 1192 8 2974 3 9292 18 7511 7 8047 19 2216 20 1991 11 5850 5 7479 12 11977 20 63 6 12325 8 7013 6 7715 5 2225 6 5161 6 9220 14 10668 9 7839 19 5285 17 7557 7 2664 13 1823 6 3766 3 7557 17 9157 6 9224 5 3799 9 10820 4 10364 6 9731 16 9634 1 3711 2 1061 8 704 1 405 3 17 4 8014 8 4445 1 4903 4 11265 18 2861 20 12261 7 1500 20 6723 7 9299 14 7574 20 5920 18 5223 6 10318 14 6469 17 6790 17 1844 18 4048 18 11912 7 5035 17 11880 13 2837 4 6373 20 1383 12 12308 14 11816 7 2600 10 6148 4 5572 14 3855 12 2960 19 2854 11 8674 6 5111 20 7973 3 3969 4 5009 15 10535 12 2267 4 10367 5 9390 11 6519 10 7310 [出力例] 8520 10423 20522 21177 30503 32501 36616 38151 32664 33751 37293 37293 37293 32961 30411 30411 23786 30104 30104 29599 24618 24618 24843 31161 35523 39382 37552 37552 39214 40843 45341 45341 50155 50155 45545 45545 45341 47050 49671 49671 49671 49204 48996 48996 47333 45598 47198 48865 48865 51846 53053 53560 53560 53560 53560 53560 53560 53560 52830 52830 52830 54461 54461 56991 56991 54461 54461 53427 53427 53427 54014 54014 54014 54014 54014 56292 56292 57854 57854 56907 56907 57238 58736 58736 58736 58736 57238 54564 54564 54564 52920 52920 52920 52920 54781 54781 55514 55514 55514 55514 |
■参照サイト
トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)