C++の練習を兼ねて, AtCoder Beginner Contest 214 の 問題E (Packing Under Range Regulations) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労した(※)ものの, 個人的には, 実装を軽くする訓練を積めたので, 非常に良かったと思う.
※提出したところ, RE, WAとなったので, 集合要素を削除する処理の廃止, 入力情報(L, R) を配列に保存する処理の廃止, を含めたロジック修正を行って, 処理を軽くして再提出して, AC版となったもの.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 214 解説 の 各リンク を ご覧下さい.
■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 89 90 91 |
// 解き直し. // https://atcoder.jp/contests/abc214/editorial/2431 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using PQ = priority_queue<int, vector<int>, greater<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 int main(){ // 1. 入力情報. int T; scanf("%d", &T); // 2. 各テストケース. rep(i, T){ // 3-1. テストケース入力情報. int N, L, R; scanf("%d", &N); set<int> st; map<int, vi> m; rep(j, N){ scanf("%d %d", &L, &R); st.insert(L); m[L].pb(R); } st.insert(1000000001); // 3-2. シミュレーション. // -> WA, RE版 の 原因と見て, L[j] を 削除(st.erase(box);) は, 実装から外すようにロジックを修正. // 箱に入れてもいいボールのリスト(以下, リストと略記) へ 追加. bool ok = true; int box = *st.begin(); PQ pq; while(box < 1000000001){ // 箱番号と同じ L[j] が 見つかったか否かで, 分岐. if(st.count(box)){ // L[j] = i の ボール j を, すべて, リスト に 追加. for(auto &q : m[box]) pq.push(q); } // ボール j を 箱 に 入れることができるか？ if(!pq.empty()){ // R[j] を 取り出す. int u = pq.top(); pq.pop(); // ボール j を 箱 に 入れることができなかった. if(u < box){ ok = false; break; } // 次の箱へ. ++box; } // リスト が 空ならば, Skip. if(pq.empty() && !st.empty()) box = *st.lower_bound(box); // ボールを全て入れることはできない場合は, 終了. if(!ok) break; } // リスト へ 追加するボールが無くなった. while(ok && !pq.empty()){ // R[j] を 取り出す. int u = pq.top(); pq.pop(); // ボール j を 箱 に 入れることができなかった. if(u < box){ ok = false; break; } // 次の箱へ. ++box; } // 3-3. 出力. 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 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 |
[入力例] 2 3 1 2 2 3 3 3 5 1 2 2 3 3 3 1 3 999999999 1000000000 [出力例] Yes No ※AtCoderテストケースより [入力例] 2 6 1 4 2 3 2 5 1 2 3 4 3 5 12 1 3 1 2 2 4 6 7 6 9 7 8 7 10 11 15 13 14 11 13 13 15 12 13 [出力例] No Yes [入力例] 2 5 1 3 2 2 3 4 4 5 1 2 7 1 5 2 3 3 3 3 4 2 5 7 8 7 9 [出力例] Yes Yes [入力例] 5 7 7 8 4 5 1 4 7 10 6 8 1 3 1 3 5 7 8 7 10 7 9 8 9 9 9 15 1 6 11 16 5 10 15 20 10 15 10 15 6 11 18 23 1 6 20 25 12 17 7 12 12 17 1 6 13 18 20 2 5 2 5 4 7 5 8 1 2 1 4 7 10 5 8 2 3 3 6 4 7 5 7 7 10 5 7 7 9 7 9 3 4 4 5 2 4 6 7 30 11 25 20 29 19 26 2 18 16 20 14 24 3 18 20 28 17 22 3 11 5 21 20 39 2 17 3 14 6 10 10 28 3 21 3 5 20 36 14 18 17 34 17 28 5 11 4 8 2 9 3 18 17 18 10 26 12 13 13 14 [出力例] Yes No Yes No Yes |
■参照サイト
AtCoder Beginner Contest 214