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; }