h_nosonの日記

競プロ、CTFなど

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

問題
Problem - E - Codeforces
対応する括弧が存在する括弧の列が与えられる.カーソルの初期位置と
R : カーソルを右にずらす
L : カーソルを左にずらす
D : 今見ている括弧と対応する括弧の間の括弧を消して右に移動する
という操作の列が与えられた時,最終的に残っている括弧の列を出力する問題.

解法
単純にシュミレーションをする.括弧の列を消すとき,次そこを通る時に飛ばして進めるように,双方向リストなどを使ってうまく間の括弧を消す必要がある.今回は,右隣の括弧の位置を表す配列nextと左隣の括弧の位置を表す配列prevを用意した.
区間[a,b]を消すとき,

next[prev[a]] = next[b];
prev[next[b]] = prev[a];

とすればいい.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int main() {
    int i, n, m, p, left;
    int next[500000];
    int prev[500000];
    string b, op, s;
    cin >> n >> m >> p;
    p--;
    rep (i,n) next[i] = i+1;
    rep (i,n) prev[i] = i-1;
    cin >> b >> op >> s;
    left = 0;
    for (auto& c : op) {
        if (c == 'R')
            p = next[p];
        else if (c == 'L')
            p = prev[p];
        else {
            int cnt = 1;
            int start = p;
            if (b[p] == '(') {
                while (cnt) {
                    p = next[p];
                    if (b[p] == '(')
                        cnt++;
                    else
                        cnt--;
                }
                if (prev[start] < 0)
                    left = next[p];
                next[prev[start]] = next[p];
                prev[next[p]] = prev[start];
                if (next[p] >= n)
                    p = prev[start];
                else
                    p = next[p];
            }
            else {
                while (cnt) {
                    p = prev[p];
                    if (b[p] == '(')
                        cnt--;
                    else
                        cnt++;
                }
                if (prev[p] < 0)
                    left = next[start];
                prev[next[start]] = prev[p];
                next[prev[p]] = next[start];
                if (next[start] >= n)
                    p = prev[p];
                else
                    p = next[start];
            }
        }
    }
    p = left;
    while (p < n) {
        cout << b[p];
        p = next[p];
    }
    cout << endl;
    return 0;
}