C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題F (Parenthesis Checking) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
2. 遅延評価セグメント木 が 復習できたので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 223 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題F/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 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 |
// 解答不能. // https://atcoder.jp/contests/abc223/editorial/2774 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<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--) const int INF = 2020202020; // AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp) // -> 一部改変(2021/10/27). template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct LazySegmentTree{ public: LazySegmentTree() : LazySegmentTree(0){} explicit LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())){} explicit LazySegmentTree(const vector<S>& v) : _n(int(v.size())){ log = 0; while((1 << log) < _n) log++; size = 1 << log; d = vector<S>(2 * size, e()); lz = vector<F>(size, id()); 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; repr(i, log, 1) push(p >> i); d[p] = x; repx(i, 1, log + 1) update(p >> i); } S get(int p){ assert(0 <= p && p < _n); p += size; repr(i, log, 1) push(p >> i); return d[p]; } S prod(int l, int r){ assert(0 <= l && l <= r && r <= _n); if(l == r) return e(); l += size; r += size; repr(i, log, 1){ if(((l >> i) << i) != l) push(l >> i); if(((r >> i) << i) != r) push((r - 1) >> i); } S sml = e(), smr = e(); 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]; } void apply(int p, F f){ assert(0 <= p && p < _n); p += size; repr(i, log, 1) push(p >> i); d[p] = mapping(f, d[p]); repx(i, 1, log + 1) update(p >> i); } void apply(int l, int r, F f){ assert(0 <= l && l <= r && r <= _n); if(l == r) return; l += size; r += size; repr(i, log, 1){ if(((l >> i) << i) != l) push(l >> i); if(((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while(l < r){ if(l & 1) all_apply(l++, f); if(r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } repx(i, 1, log + 1){ if(((l >> i) << i) != l) update(l >> i); if(((r >> i) << i) != r) update((r - 1) >> i); } } private: int _n, size, log; vector<S> d; vector<F> lz; void update(int k){ d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f){ d[k] = mapping(f, d[k]); if(k < size) lz[k] = composition(f, lz[k]); } void push(int k){ all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; int op(int a, int b){ return min(a, b); } int e(){ return INF; } int mapping(int f, int x){ return f + x; } int composition(int f, int g){ return f + g; } int id(){ return 0; } int main(){ // 1. 入力情報. int N, Q; char c[202020]; scanf("%d %d %s", &N, &Q, c); string s(c); // 2. 前処理. vi v(N + 1); rep(i, N) v[i + 1] = (s[i] == '(') ? v[i] + 1 : v[i] - 1; // 3. クエリ回答. LazySegmentTree<int, op, e, int, mapping, composition, id> seg(v); rep(i, Q){ // 3-1. クエリ情報. int t, l, r; scanf("%d %d %d", &t, &l, &r); // 3-2. パターン 1. if(t == 1){ // l文字目, r文字目更新. if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2); if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2); // l文字目, r文字目 を 入れ替え. swap(s[l - 1], s[r - 1]); } // 3-3. パターン 2. if(t == 2){ // (l - 1)文字目, r文字目 までの累積和. int lCum = seg.get(l - 1); int rCum = seg.get(r); // [l - 1, r] の 最小値. int bMin = seg.prod(l - 1, r + 1); // 出力. printf("%s\n", (bMin == lCum && lCum == rCum) ? "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 158 159 160 161 162 |
[入力例] 5 3 (())( 2 1 4 2 1 2 2 4 5 [出力例] Yes No No ※AtCoderのテストケースより [入力例] 5 3 (())( 2 1 4 1 1 4 2 1 4 [出力例] Yes No ※AtCoderのテストケースより [入力例] 8 8 (()(())) 2 2 7 2 2 8 1 2 5 2 3 4 1 3 4 1 3 5 1 1 4 1 6 8 [出力例] Yes No No ※AtCoderのテストケースより [入力例] 20 15 ()(())((((()))))(()) 2 1 2 2 3 6 1 18 19 2 7 16 2 17 20 1 5 12 2 2 7 1 6 19 1 11 15 2 8 15 1 7 13 2 13 18 1 3 16 2 5 8 2 15 20 [出力例] Yes Yes Yes Yes No No Yes No Yes [入力例] 50 20 ((()(((()(()((()))(()))(())())))))))))((()))())))) 2 19 22 1 17 20 1 7 11 2 17 20 2 18 28 2 39 44 1 15 24 1 20 39 2 24 27 2 3 26 2 40 43 1 12 31 2 22 32 2 28 29 1 9 15 2 18 23 2 13 16 1 12 37 2 45 48 1 5 8 [出力例] Yes Yes No Yes Yes No Yes No Yes No Yes No [入力例] 100 30 ()(()((()())()((())()()()()((((((())())(((()()(()))())())(()))))(())())((())((((())))))))(()))(()()( 1 37 61 2 7 12 2 30 39 1 23 61 2 25 26 1 7 50 2 9 56 2 45 56 2 77 86 1 40 73 2 28 57 1 6 11 2 47 54 1 34 65 2 40 64 2 73 76 1 6 23 2 29 65 1 15 30 1 32 42 1 43 44 2 20 27 2 44 57 1 34 60 2 26 63 1 49 58 1 17 57 2 90 93 1 30 51 2 96 99 [出力例] Yes Yes No No Yes Yes No Yes No Yes No Yes Yes No Yes Yes |
■参照サイト
AtCoder Beginner Contest 223