C++の練習を兼ねて, AtCoder Regular Contest 026 の 問題C (C – 蛍光灯) を解いてみた.
■感想.
1. 方針が全く分からなかったので, 解説を確認して, 実装したところ, 何とかAC版となった.
2. 遅延評価セグメント木が必要なため, 下記のライブラリを拝借させて頂いた.
3. 遅延評価セグメント木の復習が出来たので, 良かった思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 026 解説をご覧下さい.
■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 125 126 127 128 129 130 131 132 |
// 解き直し. // https://www.slideshare.net/chokudai/arc026 #include <bits/stdc++.h> using namespace std; using LL = long long; #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 all(x) x.begin(), x.end() #define INF 101010101010 LL dp[101010]; struct light{ int l, r; // 蛍光灯の左端, 右端. LL c; // 蛍光灯を点灯するのにかかる費用. bool operator < (const light& rhs) const{ if(l != rhs.l) return l < rhs.l; else return r > rhs.r; } }; // ※※※ 以下のライブラリを使用(一部改変) ※※※. // 遅延評価セグメント木をソラで書きたいあなたに. // http://tsutaj.hatenablog.com/entry/2017/03/30/224339 // http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2236726 struct LazySegmentTree{ private: int n; vector<LL> node, lazy; public: LazySegmentTree(vector<LL> v){ int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1, 0); // 元配列 の 値 を, セグメント木のノード に 保存. rep(i, sz) node[i + n - 1] = v[i]; repr(i, n - 2, 0) node[i] = node[i * 2 + 1] + node[i * 2 + 2]; } void eval(int k, int l, int r){ if(lazy[k] != 0) { node[k] = lazy[k]; if(r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } lazy[k] = 0; } } void update(int a, int b, LL x, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return; if(a <= l && r <= b){ lazy[k] = x; eval(k, l, r); }else{ update(a, b, x, 2 * k + 1, l, (l + r) / 2); update(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = min(node[2 * k + 1], node[2 * k + 2]); } } LL query(int a, int b, int k = 0, int l = 0, int r = -1){ if(r < 0) r = n; eval(k, l, r); if(b <= l || r <= a) return INF; if(a <= l && r <= b) return node[k]; LL vl = query(a, b, 2 * k + 1, l, (l + r) / 2); LL vr = query(a, b, 2 * k + 2, (l + r) / 2, r); return min(vl, vr); } }; int main(){ // 1. 入力情報. int N, L; scanf("%d %d", &N, &L); // 2. 蛍光灯を保存. vector<light> v; rep(i, N){ int l, r; LL c; scanf("%d %d %lld", &l, &r, &c); light x; x.l = l + 1, x.r = r + 1, x.c = c; v.pb(x); } // 以下, 解説通り. // 3. sort. sort(all(v)); // 4. 遅延伝播セグメント木を用意. LazySegmentTree seg(vector<LL>(101010, 0)); rep(i, 101010) dp[i] = INF; repx(i, 1, 101010) seg.update(i, i + 1, INF); // 5. dp更新. rep(i, N){ // 蛍光灯の情報を一つ取得. int l = v[i].l; int r = v[i].r; LL c = v[i].c; // dp[l] ～ dp[r] の 最小値 を 取得. LL tmp = seg.query(l - 1, r); // dp[r] の 更新. dp[r] = min(dp[r], tmp + c); // SegmentTree の 更新. seg.update(r - 1, r, dp[r]); // printf("l=%d r=%d c=%lld tmp=%lld\n", l, r, c, tmp); // rep(i, L + 2) printf("%lld ", seg.query(i, i + 1)); // puts(""); // rep(i, L + 2) printf("%lld ", dp[i]); // puts(""); } // 6. 出力. // rep(i, L + 2) printf("%lld ", dp[i]); // puts(""); printf("%lld\n", dp[L + 1]); 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 |
[入力例] 5 5 0 1 1 1 2 1 2 4 3 3 5 1 2 3 2 [出力例] 5 ※AtCoderのテストケースより [入力例] 8 10 0 2 1 2 3 1 0 4 1 0 2 1 3 7 1 0 10 1080 8 10 1 9 10 1 [出力例] 1080 ※AtCoderのテストケースより [入力例] 10 10 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 0 5 4 5 7 2 6 8 3 8 10 1 2 9 3 [出力例] 6 ※AtCoderのテストケースより [入力例] 5 5 0 1 100000 1 2 100000 2 3 100000 3 4 100000 4 5 100000 [出力例] 500000 ※AtCoderのテストケースより [入力例] 50 10000 0 200 45862 100 400 19945 200 600 17915 300 800 19465 400 1000 34803 500 1200 93461 600 1400 48616 700 1600 49099 800 1800 34606 900 2000 15496 1000 2200 89294 1100 2400 82648 1200 2600 89730 1300 2800 90761 1400 3000 3857 1500 3200 11030 1600 3400 51166 1700 3600 4678 1800 3800 95199 1900 4000 64122 2000 4200 19257 2100 4400 46096 2200 4600 59981 2300 4800 42505 2400 5000 46394 2500 5200 18534 2600 5400 93404 2700 5600 74100 2800 5800 4510 2900 6000 62913 3000 6200 70761 3100 6400 16118 3200 6600 24552 3300 6800 14180 3400 7000 81350 3500 7200 23663 3600 7400 56717 3700 7600 29262 3800 7800 2880 3900 8000 19465 4000 8200 73247 4100 8400 89105 4200 8600 79489 4300 8800 58709 4400 9000 14275 4500 9200 27125 4600 9400 71437 4700 9600 23357 4800 9800 88389 4900 10000 97890 [出力例] 218650 |