C++の練習を兼ねて, AtCoder Beginner Contest 038 の 問題D (プレゼント) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
※ 問題D は, 過去記事 の 実装を 書き換えた内容になっている.
2. 念のため, 箱情報について, 座標圧縮を考慮した版と, 考慮しない版とを確認して, どちらも, 問題なさそうだと分かった.
3. 個人的には, セグメント木（Range Maximum Query）の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 038 解説 を ご覧下さい.
■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 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 |
// 解き直し. // https://img.atcoder.jp/data/abc/038/editorial.pdf // 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 a first #define b second #define all(x) x.begin(), x.end() int dp[101010]; // AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp) // -> 一部改変(2021/02/05). template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{ public: SegmentTree() : SegmentTree(0){} explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){} explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){ log = 0; while((1 << log) < _n) log++; size = 1 << log; d = vector<S>(2 * size, e()); rep(i, _n) d[size + i] = v[i]; repr(i, size - 1, 1) update(i); } void set(int p, S x){ assert(0 <= p && p < _n); p += size; d[p] = x; repx(i, 1, log + 1) update(p >> i); } S get(int p){ assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r){ assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while(l < r){ if(l & 1) sml = op(sml, d[l++]); if(r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod(){ return d[1]; } private: int _n, size, log; vector<S> d; void update(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); } }; static int RMaQ_nodef(int l, int r){ return max(l, r); } static int RMaQ_ef(){ return 0; } using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp v(N); rep(i, N){ scanf("%d %d", &v[i].a, &v[i].b); v[i].b *= -1; } // 2. sort. sort(all(v)); // 3. dp更新. // -> Segment Tree の中で, Range Maximum Query として, 対応. RMaQ seg(101010); rep(i, N){ // 区間[0, -v[i].b) の 最大値 に, 1 を 加算. dp[i + 1] = seg.prod(0, -v[i].b) + 1; // 前回以前分. int bef = seg.get(-v[i].b); // dp[i + 1] を 保存. seg.set(-v[i].b, max(bef, dp[i + 1])); } // 4. 出力. // -> dp[N] ではないことに注意. printf("%d\n", seg.prod(0, 101010)); return 0; } |
■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 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 |
// AC版. // 解き直し. // https://img.atcoder.jp/data/abc/038/editorial.pdf // 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 a first #define b second #define all(x) x.begin(), x.end() #define pb push_back int dp[101010]; // AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp) // -> 一部改変(2021/02/05). template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{ public: SegmentTree() : SegmentTree(0){} explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){} explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){ log = 0; while((1 << log) < _n) log++; size = 1 << log; d = vector<S>(2 * size, e()); rep(i, _n) d[size + i] = v[i]; repr(i, size - 1, 1) update(i); } void set(int p, S x){ assert(0 <= p && p < _n); p += size; d[p] = x; repx(i, 1, log + 1) update(p >> i); } S get(int p){ assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r){ assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while(l < r){ if(l & 1) sml = op(sml, d[l++]); if(r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod(){ return d[1]; } private: int _n, size, log; vector<S> d; void update(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); } }; static int RMaQ_nodef(int l, int r){ return max(l, r); } static int RMaQ_ef(){ return 0; } using RMaQ = SegmentTree<int, RMaQ_nodef, RMaQ_ef>; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp v(N); map<int, int> ox, oy; rep(i, N){ scanf("%d %d", &v[i].a, &v[i].b); ox[v[i].a] = 0; oy[v[i].b] = 0; } // 2. 座標圧縮. int idx = 0; for(auto &p : ox) p.b = ++idx; idx = 0; for(auto &p : oy) p.b = ++idx; // 3. 箱情報修正. vp boxes; for(auto &p : v) boxes.pb({ox[p.a], -oy[p.b]}); // 4. sort. sort(all(boxes)); // 5. dp更新. // -> Segment Tree の中で, Range Maximum Query として, 対応. RMaQ seg(101010); rep(i, N){ // 区間[0, -v[i].b) の 最大値 に, 1 を 加算. dp[i + 1] = seg.prod(0, -boxes[i].b) + 1; // 前回以前分. int bef = seg.get(-boxes[i].b); // dp[i + 1] を 保存. seg.set(-boxes[i].b, max(bef, dp[i + 1])); } // 6. 出力. // -> dp[N] ではないことに注意. printf("%d\n", seg.prod(0, 101010)); 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 |
[入力例] 5 8 8 5 3 2 2 4 2 2 1 ※AtCoderテストケースより [出力例] 4 [入力例] 8 3 1000 2 3 3 4 2 999 4 7 5 4 1 998 1 2 [出力例] 4 [入力例] 10 1 2 2 3 5 6 3 4 4 3 4 7 8 9 10 12 7 8 4 4 [出力例] 7 [入力例] 20 116 95 98 55 32 25 10 77 34 4 107 91 84 68 29 81 59 48 13 2 79 49 102 32 61 7 87 72 98 2 57 10 30 111 95 80 80 71 22 90 [出力例] 10 [入力例] 100 6031 2801 10151 8318 2192 3196 2379 5492 10246 11130 10065 10946 7763 8183 5729 6839 5341 9782 7726 10238 10825 10302 1604 5527 4842 6474 1393 7985 2584 12054 7045 10173 8557 6642 3391 6095 3499 2723 5252 3927 10494 9438 8839 766 3722 10274 7664 11264 812 1194 1154 3009 10013 10308 5285 9462 4586 3170 12060 2236 4342 5614 11035 8784 4231 11163 1980 3499 2316 10547 6582 1417 3239 4104 1381 7185 9779 8737 11792 10898 6135 5841 6292 46 3056 7476 1625 5051 10917 1602 2583 5298 12313 3842 53 8354 10625 4448 11271 584 4941 11890 6551 11988 7659 12104 11194 1147 9745 4446 9172 9747 4449 6324 10246 2878 3616 1752 3451 9236 3599 10505 6948 10871 4468 1146 148 12336 6728 1059 4602 4125 3056 3552 4651 9292 8904 11572 11476 11109 7336 8777 6145 9292 4917 9631 530 678 4333 11569 7502 3835 10436 7692 1838 3656 10749 8330 10101 1870 7952 2956 12261 4401 10132 3537 10100 5929 5591 10414 10089 986 3844 10329 8708 6312 2093 2806 11288 9057 6507 11709 9249 3108 3487 8066 7628 11532 1169 10729 6629 2277 2563 4960 440 3836 11544 11883 12215 875 [出力例] 17 |
■参照サイト
AtCoder Beginner Contest 038
パ研合宿2020 第1日「SpeedRun」／N – 背の順 解説／セグメント木（Range Minimum Query）の使い方を参考にしました