C++の練習を兼ねて, AtCoder Beginner Contest 137 の 問題D (D – Summer Vacation) を解いてみた.
■感想.
1. 時間かかってしまったが, 正答に辿り着けたので良かったと思う.
2. 時間を見つけて, 引き続き, 復習を進めたいと思う.
本家のサイトABC 137解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; const int MAX = 100001; vector<vector<int>> A(MAX); int reward[MAX]; int main(){ // 1. 入力情報取得. int N, M; scanf("%d %d", &N, &M); for(int i = 0; i < N; i++){ int a, b; scanf("%d %d", &a, &b); if(a <= M) A[a].push_back(b); } // 2. どの仕事を請けるか確定させる. // (報酬支払日／仕事開始日) // No.1 M 日後 : 0日目 // No.2 M - 1 日後 : 1日目まで. // No.3 M - 2 日後 : 2日目まで. // No.4 M - 3 日後 : 3日目まで. // ... // No.M 1 日後 : M - 1日目まで. // -> 仕事開始日が最も遅い, No.M から順に, 仕事出来るかどうかを決めていく. // -> 具体的には, 以下の流れで, 仕事を請けるか決定していくイメージ. // No.M の 仕事 が, X(M)件 あれば, 一番報酬 の 大きい仕事 を 請ける. // No.(M - 1) の 仕事 が, X(M - 1)件 あれば, No.M の 残りの仕事 と 併せて, 一番報酬の大きい仕事を引き受ける. // 以下, 繰り返し. // ※N件の制約事項は, 4. で対応. priority_queue<int> pq; for(int d = M - 1; d >= 0; d--){ // 2-1. d日目で, 可能な仕事の報酬を取得. for(auto &r : A[M - d]) pq.push(r); // 2-2. 仕事があれば, 報酬情報(1件)を, rewardテーブルに登録. if(pq.size() > 0){ int r = pq.top(); pq.pop(); reward[d] = r; } } // 3. 報酬の大きい順に並べ替える. sort(reward, reward + MAX, greater<int>()); // 4. 最大 N件 まで請けた場合に, 報酬の最大値を計算. int ans = 0; for(int i = 0; i < N; i++) ans += reward[i]; // 5. 出力 ～ 後処理. 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 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 |
[入力例] 3 4 4 3 4 1 2 2 [出力例] 5 ※AtCoderテストケースより [入力例] 5 3 1 2 1 3 1 4 2 1 2 3 [出力例] 10 ※AtCoderテストケースより [入力例] 1 1 2 1 [出力例] 0 ※AtCoderテストケースより [入力例] 120 130 62 3069 80 1908 38 333 104 3996 84 1644 50 6381 8 926 79 8063 3 3741 36 3288 76 6322 37 5784 38 7903 11 624 18 7040 67 6759 39 3002 14 843 45 5747 127 4828 92 2457 24 924 48 2116 119 2812 67 3782 83 7753 47 3421 73 169 15 6777 128 3209 98 4195 65 6485 20 2279 64 5393 78 6565 33 9644 28 7896 122 8236 42 8079 43 1875 24 3215 99 2206 40 3220 24 9879 126 2404 90 5148 91 6315 101 7658 22 5949 68 9861 6 2824 117 7105 23 6462 62 6703 60 5626 130 136 105 5060 15 3840 116 2945 10 3352 127 4674 76 9812 56 3277 129 1876 106 2237 119 6767 84 9951 81 629 41 3058 31 6328 129 520 24 9553 16 1919 125 7767 6 876 20 9750 111 8756 67 4480 125 7542 83 2216 76 2277 113 492 61 243 119 3425 12 7591 9 2479 92 8487 96 9414 58 7189 127 3710 82 2984 45 2355 105 7015 26 3590 107 8135 129 7670 114 9993 56 5309 78 4641 43 9680 65 10 79 2929 122 4441 40 4609 99 3202 60 2421 33 1313 89 5185 121 1152 10 7686 105 3877 24 1457 105 5262 4 4318 106 7050 5 794 88 5142 21 176 41 9411 15 2867 [出力例] 550000 [入力例] 100 70 62 2429 80 2233 38 1095 1 10000 84 10000 50 416 8 1676 79 10000 3 1068 36 2391 2 10000 37 1806 38 6454 11 880 18 3582 2 10000 39 2655 14 1305 45 7746 1 3770 92 8690 24 2501 48 10000 1 9999 67 6701 83 9999 47 6328 73 8211 15 9999 1 9827 98 3411 65 395 20 5641 64 9841 78 927 33 2220 28 7678 1 4802 42 2803 43 9675 24 6213 99 3858 40 9998 24 1154 126 3544 90 4348 91 1709 101 303 22 6851 68 565 6 7796 117 9620 23 9664 62 3585 60 9998 130 9997 2 6753 15 7639 116 8744 10 5263 2 3070 76 9996 56 2920 129 1686 106 593 2 3231 84 9000 81 811 41 2578 31 7434 129 3103 24 5876 16 5730 125 3088 6 6263 20 8000 111 6622 67 7167 125 4251 83 4461 76 2442 113 4417 61 7609 119 7000 12 6130 9 7323 92 7725 96 3250 58 5112 127 2863 82 5680 45 5905 105 6789 26 5130 107 5142 129 551 114 9341 56 5027 78 5425 43 9876 [出力例] 345543 |
■参照サイト
AtCoder Beginner Contest 137