Codeforces Round #350 Div2 E: Correct Bracket Sequence Editor

問題

Problem - E - Codeforces

解法

愚直シミュレーション

コード

#include <bits/stdc++.h>
using namespace std;

string S;
map<int, int> tree_map;

int dfs(int pos) {
  if (pos == S.size()) return pos;
  if (S[pos] == '(') {
    int right = dfs(pos + 1);
    tree_map[pos] = right;
    return dfs(right + 1);
  } else {
    return pos;
  }
}

int delete_in(int pos, set<int> &right_set) {
  auto it = tree_map.lower_bound(pos);
  int left = it->second;
  while (true) {
    auto it2 = tree_map.lower_bound(pos);
    if (it2 != tree_map.end() && it2->second <= left) {
      right_set.erase(it2->second);
      tree_map.erase(it2);
    } else {
      break;
    }
  }
  auto it_left = tree_map.lower_bound(pos);
  auto it_right = right_set.lower_bound(pos);
  if (it_left == tree_map.end() && it_right == right_set.end()) {
    it_right--;
    pos = *it_right;
  } else if (it_left == tree_map.end()) {
    pos = *it_right;
  } else {
    pos = min(it_left->first, *it_right);
  }
  return pos;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M, pos;
  cin >> N >> M >> pos;
  pos--;
  cin >> S;
  string input;
  cin >> input;
  dfs(0);
  vector<int> pairs(N);
  for (const auto &p : tree_map) {
    pairs[p.first] = p.second;
    pairs[p.second] = p.first;
  }
  set<int> right_set;
  for (int i = 0; i < N; ++i) {
    if (S[i] == ')') right_set.insert(i);
  }

  for (int i = 0; i < M; ++i) {
    if (S[pos] == '(') {
      if (input[i] == 'L') {
        auto it_left = tree_map.lower_bound(pos);
        auto it_right = right_set.lower_bound(pos);
        it_left--;
        if (it_right == right_set.begin()) {
          pos = it_left->first;
        } else {
          it_right--;
          pos = max(it_left->first, *it_right);
        }
      } else if (input[i] == 'R') {
        auto it_left = tree_map.lower_bound(pos);
        auto it_right = right_set.lower_bound(pos);
        it_left++;
        if (it_left == tree_map.end()) {
          pos = *it_right;
        } else {
          pos = min(it_left->first, *it_right);
        }
      } else {  //'D'
        pos = delete_in(pos, right_set);
      }
    } else {
      // when ')'
      if (input[i] == 'L') {
        auto it_left = tree_map.lower_bound(pos);
        auto it_right = right_set.lower_bound(pos);
        it_left--;
        if (it_right == right_set.begin()) {
          pos = it_left->first;
        } else {
          it_right--;
          pos = max(it_left->first, *it_right);
        }
      } else if (input[i] == 'R') {
        auto it_right = right_set.lower_bound(pos);
        it_right++;
        auto it_left = tree_map.lower_bound(pos);
        if (it_left == tree_map.end()) {
          pos = *it_right;
        } else {
          pos = min(it_left->first, *it_right);
        }
      } else {
        pos = delete_in(pairs[pos], right_set);
      }
    }

    // DEBUG
    // cerr << pos << endl;
    // for (const auto &p : tree_map) {
    //   cerr << p << endl;
    // }
  }

  vector<bool> e(N, false);
  for (const auto &p : tree_map) {
    e[p.first] = true;
    e[p.second] = true;
  }
  string ans = "";
  for (int i = 0; i < N; ++i) {
    if (e[i]) ans += S[i];
  }
  cout << ans << endl;
}