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

問題概要
"("と")"の２種類の文字からなる文字列がある。
この文字列は括弧表現として正しい。
以下の何れかのクエリが与えられる。

• L: カーソルの左に動かす
• R: カーソルを右に動かす
• D: カーソルが指している括弧とそれに対応する括弧の閉区間をすべて削除する

すべてのクエリ処理を行った後の文字列を求めよ。

解法
頑張っていろいろ実装してもいいけど、双方向リストを使って書くのが簡単。
C++の場合は、STLのlistが使える。list.erase()の戻り値は、削除された要素の一つ後ろのiteratorなので、それをそのまま使える。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n, m, p;
char s[500000+1];
char op[500000+1];
int pr[500000];

void set_pairs() {
  stack <int> stk;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      stk.push(i);
    else {
      int j = stk.top();
      stk.pop();
      pr[i] = j;
      pr[j] = i;
    }
  }
}

void solve() {
  set_pairs();
  
  list<int> lst;
  for (int i = 0; i < n; i++)
    lst.push_back(i);

  --p;
  auto itr = lst.begin();
  while (*itr != p)
    ++itr;

  for (int i = 0; i < m; i++) {
    if (op[i] == 'L')
      --itr;
    else if (op[i] == 'R')
      ++itr;
    else {
      auto ltr = itr;
      auto rtr = itr;

      if (s[*itr] == '(') {
        while (*rtr != pr[*itr])
          ++rtr;
      } else {
        while (*ltr != pr[*itr])
          --ltr;
      }

      itr = lst.erase(ltr, ++rtr);
      if (itr == lst.end())
        --itr;
    }
  }

  string ret;
  for (auto &x: lst)
    ret += s[x];
  printf("%s\n", ret.c_str());
}

int main() {
  scanf(" %d %d %d", &n, &m, &p);
  scanf(" %s", s);
  scanf(" %s", op);
  solve();
  return 0;
}