C++の練習を兼ねて, AtCoder Regular Contest 032 の 問題C (C – 仕事計画) を解いてみた.
■感想.
1. 解答方針が見えなかったので, 解説を参照して実装したところ, 実装に非常に苦労したものの(※)ようやくAC版となった.
※ 同じ仕事の開始時刻が, 複数回出現する場合を考慮したところ, dp更新式が, 複雑になってしまった.
2. 苦手な, dpの訓練が出来たので, 非常に良かったと思った.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 032 解説をご覧下さい.
■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 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 |
// 解き直し. // https://www.slideshare.net/chokudai/arc032 #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; #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() const int MAX = 1010101; P dp[MAX]; // {時刻i以降での最大仕事数, 次の仕事の最小番号} struct job{ int s, e, i; // 仕事の開始, 終了, 仕事の番号. bool operator < (const job& rhs) const{ return (s != rhs.s) ? (s < rhs.s) : (e < rhs.e); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); priority_queue<job> pq; vector<P> v; // 入力データ保存用. // map<P, int> m; rep(i, N){ int s, e; job j; scanf("%d %d", &s, &e); j.s = s; j.e = e; j.i = i + 1; pq.push(j); v.pb({s, e}); // m[{s, e}]++; } // while(!pq.empty()){ // job j = pq.top(); // pq.pop(); // printf("%d %d %d\n", j.s, j.e, j.i); // } // printf("m.size()=%d\n", m.size()); // ※ 以下, 解説通り. // 2. dp更新. repr(i, MAX - 2, 0){ while(!pq.empty()){ // 仕事情報を一つ取ってくる. job j = pq.top(); // 開始時刻が, 異なったら, Skip. if(j.s != i) break; // 仕事情報を使う場合. P ok = {dp[j.e].a + 1, j.i}; // 仕事情報を使わない場合. P ng = {dp[j.s + 1].a, dp[j.s + 1].b}; // 現在のdp情報. P cur = dp[j.s]; // ok, ng, cur を 比較して, dp更新. if(cur.b == 0){ if(ok.a == ng.a) dp[j.s] = (ok.b < ng.b) ? ok : ng; else dp[j.s] = (ok.a > ng.a) ? ok : ng; }else{ if(ok.a == ng.a){ if(ok.a > cur.a) dp[j.s] = (ok.b < ng.b) ? ok : ng; if(ok.a == cur.a) dp[j.s] = {ok.a, min({ok.b, ng.b, cur.b})}; }else{ if(ok.a > ng.a){ if(ok.a > cur.a) dp[j.s] = ok; if(ok.a == cur.a) dp[j.s] = {ok.a, min(ok.b, cur.b)}; } if(ng.a > ok.a){ if(ng.a > cur.a) dp[j.s] = ng; if(ng.a == cur.a) dp[j.s] = {ng.a, min(ng.b, cur.b)}; } } } // 仕事情報を削除して, 次処理へ. pq.pop(); } // dp更新(※未更新の場合). if(dp[i].a == 0) dp[i] = dp[i + 1]; } // rep(i, 20) printf("%d %d\n", dp[i].a, dp[i].b); // 3. 復元. vector<int> ans; int cur = dp[0].b; while(1){ // 仕事番号を保存. ans.pb(cur); // 仕事情報取得. P p = v[cur - 1]; // 仕事番号を更新. cur = dp[p.b].b; // 終了条件. if(!cur) break; } // 4. 出力. printf("%d\n", dp[0].a); int l = ans.size(); rep(i, l){ printf("%d", ans[i]); if(i < l - 1) printf(" "); } puts(""); 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 |
[入力例] 4 0 5 0 3 3 7 5 10 [出力例] 2 1 4 ※AtCoderのテストケースより [入力例] 5 0 5 0 3 3 7 5 10 7 12 [出力例] 3 2 3 5 ※AtCoderのテストケースより [入力例] 8 1 5 3 9 2 5 1 2 8 10 9 11 7 15 10 14 [出力例] 4 4 3 5 8 ※AtCoderのテストケースより [入力例] 3 5 6 0 1 2 3 [出力例] 3 2 3 1 [入力例] 8 0 2 0 5 0 3 3 7 3 9 8 10 8 12 11 15 [出力例] 4 1 4 6 8 [入力例] 30 4 17 1 21 10 31 13 18 12 25 8 16 6 25 2 21 4 15 5 17 10 25 2 19 4 21 10 17 5 26 10 32 14 15 13 33 4 11 5 22 2 22 12 19 3 14 10 15 13 24 11 13 2 27 2 14 2 25 4 27 [出力例] 3 19 26 4 [入力例] 100 666 3011 384 706 1140 3366 483 1655 1010 2579 439 2528 424 1299 735 2607 80 975 190 646 789 1932 844 3062 466 2043 117 1398 556 2773 90 1559 803 844 516 1882 690 1122 564 856 335 2453 600 825 1214 1773 500 2764 122 980 987 2000 997 1096 1083 1498 314 472 623 2005 1072 2768 628 1022 462 1091 1004 2769 265 1842 3 882 650 2142 873 2527 985 1101 937 2112 1093 1275 160 963 703 2274 669 1038 739 1313 342 2252 469 1466 898 1885 959 1721 76 1196 1144 1540 1166 3250 1150 1307 48 1031 1116 2138 415 587 133 309 119 2276 70 2013 828 2003 1033 3349 481 1457 1031 2804 1166 1552 170 1293 297 1521 90 741 375 2238 486 1837 446 1764 105 2045 870 2801 1051 2974 552 2231 403 556 806 2106 1058 2264 1179 2751 260 2008 588 1264 818 1882 697 1409 290 745 626 2124 745 783 1001 2328 552 2299 58 1731 936 2060 166 1317 981 1609 417 1506 435 1270 859 2658 972 1397 379 466 145 603 579 1456 140 631 700 2209 [出力例] 6 57 2 85 17 27 3 |
■参照サイト
AtCoder Regular Contest 032