mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

問題

codeforces.com

例によって正しいかっこ列 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] の場合を書きます。
    • [p, pa[p]] の区間が消えるので, p の左側のかっこのすぐ右側にある index l[p] は, pa[p] のすぐ右側にある index r[pa[p]] と対応するようになります。r[pa[p]] の対応は l[p] です。最後に, p は ふつう r[pa[p]] に移りますが, これが 外にはみ出している場合は 左側 l[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;
}