裏紙

ほぼ競プロ、たまに日記

CF 670 E - Correct Bracket Sequence Editor

問題

Problem - E - Codeforces

問題概要

Correct Bracket Sequence(CBS)という文字列のみに対して動作するテキストエディタを考える。CBSとは、()の2種類の文字のみで構成される文字列であり、全てのカッコの開閉が1つ1つ対応付けられているものである(()の数が一致し、どんなprefixを取っても(の数より)の数が多くなることはありえない)。

このCBSに対して、エディタは以下の3つの操作をすることが出来る。

  • L : カーソルを左に移動。
  • R : カーソルを右に移動。
  • D : 今カーソルがあるところに注目し、その括弧が対応している区間の文字を全て削除する。削除後のカーソルの位置は、そのカーソルの位置から右にまだ削除されていない文字のうちで最も近い位置に来る。そのような文字がないときは、そのカーソルの位置から左でまだ削除されていない文字の打ちで最も近い位置に来る。

最初のCBSの状態と操作の命令列と初期カーソル位置が与えられるので、すべての操作を終えた後のCBSがどうなっているかを答えよ。

イデア

まず、愚直にシミュレーションするのは間に合わないので、既に削除した文字をうまくスキップしたりする工夫が必要であると考える。

まず、どの括弧どうしが対応しているのかを調べておく。i番目の括弧が対応している位置をpos_iで表す。これは、スタックを利用すると簡単に計算できる。先頭から順に見ていって、(が来たらスタックに積み、)が来たらスタックの先頭を取り出して(vとする)、現在の位置とそれが対応づいていると言うことができるので、pos_v = ipos_i = vと更新すれば良い。

また、leftrightという配列を用意して、「まだ削除されていないiより左にある括弧のうちで最も近いものの位置」と「まだ削除されていないiより右にある括弧のうちで最も近いものの位置」を保存するものとする。もしそれに対応するものがないときには-1とする。

現在のカーソル位置をpで表す。そして、命令列を順番に見ていく:

  • Lのとき、Rのとき

左端にあるときにLや右端にあるときにRが来ることはないという制約があるので、絶対に移動する。よって、それぞれp = left_pp = right_pとすれば良い。

  • Dのとき

まずは、対応する括弧の位置を調べるために、lf=prg=pos_pとする。ここでlf \gt rgならswapしておく。すると、今回の削除で消える区間は [ lf , rg ]ということになる。 そして、right_{rg}-1なら消去後のカーソルは今より左側に来ることになる(つまり、p=left_{lf}となる)。そうでない時には、p=right_{rg}とすればよい。

また、この部分文字列の削除によって、leftrightの更新を行う必要がある。 [ lf , rg ]が削除される区間になるが、削除される区間よりも左にまだ削除されていない括弧があればrg+1から順に見ていって一番最初に見つけた位置がright_{left [ lf ] } になり、削除される区間よりも右にまだ削除されていない括弧があればlf-1から見ていって一番最初に見つけた位置をleft_{ right [ rg ] }と更新すれば良い。

最後の出力はrightをたどっていけば出力出来る。スタート地点はleftを参考に、最後から探して行ってleft=-1に初めてなる地点をスタートとするとよい。

実装(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;
}