Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor
問題
例によって正しいかっこ列 CBS を定める。
このかっこ列に対して, あるポインタ p から次のように操作をしていく。
- L: p を 1 つ左に移動させる。
- R: p を 1 つ右に移動させる。
- D: p に対応するかっこが必ずある。p 番目のかっことそれに対応するかっこ, およびその間にあるかっこをすべて取り除く。その後, もし p の右側に かっこがあるなら p を右にずらし, ないなら p を左にずらす。
操作順が並べられるので, 最終的にできるかっこ列を求めよ。
解法
まず前計算して pa[p] = (p に対応するかっこのある位置) を求めておきます。
解法としては, 取り除かれた区間を無視するように工夫しながら各操作を O(1) でやっていくイメージです。
l[p] = (p のすぐ左側にある index), r[p] = (p のすぐ右側にある index) というのを動かしていきます。最初は l[p] = p-1, r[p] = p+1 ですね。で,
- L: p = l[p] とします。
- R: p = r[p] とします。
- D: p < pa[p] の場合を書きます。
const int MAXN = 500500; int l[MAXN], r[MAXN], pa[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m, p; cin >> n >> m >> p; string s; cin >> s; stack<int> st; for (int i = 1; i <= n; i++) { if (s[i-1] == '(') st.push(i); else { int c = st.top(); st.pop(); pa[c] = i, pa[i] = c; } } assert(st.empty()); for (int i = 0; i <= n; i++) { l[i] = i-1, r[i] = i+1; } string op; cin >> op; for (int i = 0; i < m; i++) { if (op[i] == 'L') { p = l[p]; } else if (op[i] == 'R') { p = r[p]; } else { if (p < pa[p]) { r[l[p]] = r[pa[p]]; l[r[pa[p]]] = l[p]; if (r[pa[p]] <= n) p = r[pa[p]]; else p = l[p]; } else { // pa[p] < p r[l[pa[p]]] = r[p]; l[r[p]] = l[pa[p]]; if (r[p] <= n) p = r[p]; else p = l[pa[p]]; } } } for (int i = r[0]; i <= n; i = r[i]) cout << s[i-1]; cout << endl; return 0; }