CF 670 E - Correct Bracket Sequence Editor
問題
問題概要
Correct Bracket Sequence(CBS)
という文字列のみに対して動作するテキストエディタを考える。CBS
とは、(
と)
の2種類の文字のみで構成される文字列であり、全てのカッコの開閉が1つ1つ対応付けられているものである((
と)
の数が一致し、どんなprefixを取っても(
の数より)
の数が多くなることはありえない)。
このCBS
に対して、エディタは以下の3つの操作をすることが出来る。
L
: カーソルを左に移動。R
: カーソルを右に移動。D
: 今カーソルがあるところに注目し、その括弧が対応している区間の文字を全て削除する。削除後のカーソルの位置は、そのカーソルの位置から右にまだ削除されていない文字のうちで最も近い位置に来る。そのような文字がないときは、そのカーソルの位置から左でまだ削除されていない文字の打ちで最も近い位置に来る。
最初のCBS
の状態と操作の命令列と初期カーソル位置が与えられるので、すべての操作を終えた後のCBS
がどうなっているかを答えよ。
アイデア
まず、愚直にシミュレーションするのは間に合わないので、既に削除した文字をうまくスキップしたりする工夫が必要であると考える。
まず、どの括弧どうしが対応しているのかを調べておく。番目の括弧が対応している位置をで表す。これは、スタックを利用すると簡単に計算できる。先頭から順に見ていって、(
が来たらスタックに積み、)
が来たらスタックの先頭を取り出して(とする)、現在の位置とそれが対応づいていると言うことができるので、、と更新すれば良い。
また、とという配列を用意して、「まだ削除されていないより左にある括弧のうちで最も近いものの位置」と「まだ削除されていないより右にある括弧のうちで最も近いものの位置」を保存するものとする。もしそれに対応するものがないときにはとする。
現在のカーソル位置をで表す。そして、命令列を順番に見ていく:
L
のとき、R
のとき
左端にあるときにL
や右端にあるときにR
が来ることはないという制約があるので、絶対に移動する。よって、それぞれ、とすれば良い。
D
のとき
まずは、対応する括弧の位置を調べるために、、とする。ここでならswapしておく。すると、今回の削除で消える区間は ]ということになる。 そして、がなら消去後のカーソルは今より左側に来ることになる(つまり、となる)。そうでない時には、とすればよい。
また、この部分文字列の削除によって、との更新を行う必要がある。 ]が削除される区間になるが、削除される区間よりも左にまだ削除されていない括弧があればから順に見ていって一番最初に見つけた位置がになり、削除される区間よりも右にまだ削除されていない括弧があればから見ていって一番最初に見つけた位置をと更新すれば良い。
最後の出力はをたどっていけば出力出来る。スタート地点はを参考に、最後から探して行ってに初めてなる地点をスタートとするとよい。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define mp make_pair #define pb push_back #define fi first #define se second int main() { int n,m,p; string cbs,op; cin >>n >>m >>p; cin >>cbs; cin >>op; --p; stack<int> st; //対応付け vector<int> pos(n); rep(i,n) { if(cbs[i]=='(') st.push(i); else { int v=st.top(); st.pop(); pos[v]=i; pos[i]=v; } } int left[500000],right[500000]; rep(i,n) left[i]=i-1; rep(i,n) right[i]=i+1; right[n-1]=-1; rep(i,m) { if(op[i]=='L') p=left[p]; else if(op[i]=='R') p=right[p]; else { int lf=p; int rg=pos[p]; if(lf>rg) swap(lf,rg); if(right[rg]==-1) p=left[lf]; else p=right[rg]; //括弧の結合の更新 right[left[lf]]=right[rg]; left[right[rg]]=left[lf]; } } //rep(i,n) printf("%d: left: %d, right: %d\n",i,left[i],right[i]); int idx=n-1; while(left[idx]!=-1) --idx; while(idx!=-1) { printf("%c",cbs[idx]); idx=right[idx]; } printf("\n"); return 0; }