C++の練習を兼ねて, AtCoder Beginner Contest 245 の 問題E (Wrapping Chocolate) を解いてみた.
■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 判定可能であることが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 245 解説 の 各リンク を ご覧下さい.
■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 |
// 解き直し. // https://atcoder.jp/contests/abc245/editorial/3635 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using T3 = tuple<int, int, int>; using vt = vector<T3>; #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 all(x) x.begin(), x.end() int a[202020], b[202020], c[202020], d[202020]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); rep(i, N) scanf("%d", &a[i]); rep(i, N) scanf("%d", &b[i]); rep(i, M) scanf("%d", &c[i]); rep(i, M) scanf("%d", &d[i]); // 2. sort. vt v; rep(i, N) v.emplace_back(a[i], b[i], 0); rep(i, M) v.emplace_back(c[i], d[i], 1); sort(all(v)); reverse(all(v)); // 3. 判定. multiset<int> mst; bool ok = true; for(auto &t : v){ // 要素(チョコレート or 箱). int h = get<0>(t); int w = get<1>(t); int f = get<2>(t); // 箱. if(f){ mst.insert(w); continue; } // チョコレート. auto it = mst.lower_bound(w); if(it == mst.end()){ ok = false; break; } mst.erase(mst.find(*it)); } // 4. 出力. printf("%s\n", ok ? "Yes" : "No"); 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 |
[入力例] 2 3 2 4 3 2 8 1 5 2 10 5 [出力例] Yes ※AtCoderテストケースより [入力例] 2 2 1 1 2 2 100 1 100 1 [出力例] No ※AtCoderテストケースより [入力例] 1 1 10 100 100 10 [出力例] No ※AtCoderテストケースより [入力例] 1 1 10 100 10 100 [出力例] Yes ※AtCoderテストケースより [入力例] 5 7 1 6 12 2 12 13 10 9 3 11 7 6 2 12 9 6 12 9 7 7 10 12 11 13 [出力例] No [入力例] 10 18 54 111 86 23 17 51 87 19 88 37 110 107 53 58 13 33 58 9 63 71 115 68 18 121 86 26 87 93 104 2 67 3 92 117 52 57 102 102 10 123 36 39 91 52 56 106 84 18 67 62 76 107 75 118 63 63 [出力例] Yes [入力例] 20 25 867 1461 1449 999 1542 1320 1193 942 1367 1507 1100 516 1226 1234 1092 1445 1216 857 1214 686 1348 1520 567 555 730 1300 1089 717 1488 739 890 959 566 863 1610 804 1731 940 1393 1030 1001 1574 1819 2022 1169 1729 1428 1339 1113 1648 535 697 1310 1088 1425 599 1444 999 1306 576 783 942 2020 1450 1320 713 999 1389 2023 555 1521 1381 628 1258 731 1693 999 594 1516 1527 1099 1359 1276 1393 1235 1591 1595 1688 732 1165 [出力例] Yes |
■参照サイト
AtCoder Beginner Contest 245