Codeforces Round #374 (Div. 2) C. Journey

問題
n個の名所がある。
名所間を移動するのに必要な時間が与えられる。
1つ目の名所からスタートして、時間T以内にn個目の名所に辿りつかないといけない。
なるべく多くの名所を周りたい場合、どのような順番で名所を訪れればよいか出力せよ。

解法
本番はダイクストラをした。
他の人のソース見たら、みんなトポロジカル順序でDPしてて焦った。
絶対落ちたわーと絶望していたら通っていた。
が、この問題はトポロジカル順序DPで解いた方がかっこいい。

ソース

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

const int INF = 1<<30;
int n, m, t;
int dp[5050][5050];  // dp[i][j]: at j-th place and visited i+1 place
int pre[5500][5050];
vector<pair<int, int> > edges[5050];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m >> t;
  REP (i, m) {
    int v,u,w;
    cin >> v >> u >> w;
    edges[--v].emplace_back(--u, w);
  }

  REP (i, 5050) REP (j, 5050) { dp[i][j] = INF; pre[i][j] = -1; }
  dp[0][0] = 0;

  REP (i, n) REP (j, n) {
    if (dp[i][j] == INF) continue;
    for (auto &e : edges[j]) {
      int k, w;
      tie(k, w) = e;
      if (dp[i][j] + w < dp[i+1][k]) {
        dp[i+1][k] = dp[i][j] + w;
        pre[i+1][k] = j;
      }
    }
  }

  int v = n-1;
  int c = -1;
  REP (i, n) if (dp[i][v] <= t) c = i;

  vector<int> r;
  while (v) {
    r.push_back(v+1);
    v = pre[c--][v];
  }
  r.push_back(1);
  reverse(ALL(r));

  cout << r.size() << endl;
  for (auto &x: r)
    cout << x << " ";
  cout << endl;

  return 0;
}

Centroid Decompositionの問題

Centroid Decompositionを使う問題をいくつか解いてみた。
Centroidが何なのか知らない人はこちら。

Codeforces Round #190 Ciel the Commander

問題
木の各ノードにアルファベット（A-Z）を1つ書きたい。
ただし、同じアルファベットが書かれた2つのノードv, w間のパス上には、2つのノードに書かれたアルファベットより小さい文字が書かれたノードが存在しなければならない。
このようなアルファベットの書き方を求めよ。

解法
Centroid Decompositionして分解されたときの再帰の深さの順に小さい文字を割り振っていけばOK。

ソースコード

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

int n;
vector<int> edges[100000];
int rk[100000];
int sz[100000];

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &w: edges[v]) {
    if (rk[w] || w == par) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  for (auto &w: edges[v]) {
    if (rk[w] || w == par) continue;
    if (2 * sz[w] > total)
      return centroid(w, v, total);
  }
  return v;
}

void solve(int v, int r) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  rk[v] = r;
  for (auto &w: edges[v]) {
    if (rk[w]) continue;
    solve(w, r+1);
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  REP (i, n-1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  solve(0, 1);
  REP (i, n) {
    char c = 'A' + rk[i] - 1;
    cout << c << " ";
  }
  cout << endl;
  
  return 0;
}

Codeforces Round #199 Xenia and Tree

問題
木のノードに色を塗る。はじめノード1は赤色に、それ以外のノードは青色に塗られている。以下のクエリを高速に処理せよ。
1. ある青いノードを赤色に塗る
2. あるノードから赤色のノードまでの最短距離を求める

解法
Centroid Decompositionを使って、バランスした木に構築する。
1. のクエリに対しては指定されたノードを赤く塗り、そのノードからルート方向へ登りながら、 通過したノードにそのノードからそのノード以下の赤ノードまでの最短距離を更新する。
2. のクエリに対してはそのノードからルート方向へ登りながら1.のときに更新した値を用いて最短距離を計算する。
木がバランスしているので、訪れるノード数がlog(n)個程度になるのがポイント。

Centroid Decompositionで作った木と元の木のノード集合は同じだが、枝集合は異なることに注意。ノード間の距離を求める場合は元の木における距離を使わないといけない。

ソースコード

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

class LCA {
  int V, logV;
  vector<int> depth;
  vector<vector<int> > parent;
  
  void build() {
    for (int k = 0; k + 1 < logV; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0) parent[k+1][v] = -1;
        else parent[k+1][v] = parent[k][parent[k][v]];
      }
    }
  }
public:
  LCA(int V) {
    this->V = V;
    logV = 0;
    while (V > (1LL<<logV)) logV++;
    this->depth = vector<int>(V);
    this->parent = vector<vector<int> >(logV, vector<int>(V));
  }
  
  void init(int N, int p[], int d[]) {
    for (int i = 0; i < N; i++) {
      parent[0][i] = p[i];
      depth[i] = d[i];
    }
    this->build();
  }
  
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logV; k++) {
      if ((depth[v] - depth[u]) >> k & 1)
        v = parent[k][v];
    }
    if (u == v) return u;
    
    for (int k = logV-1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

const int INF = 1<<28;
int n, m;
vector<int> edges[100000];
bool vis[100000];
int p[100000];
int sz[100000];
bool red[100000];
int dist[100000];
int lcap[100000];
int lcad[100000];
LCA lca(100000);

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &w: edges[v]) {
    if (vis[w] || w == par) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  for (auto &w: edges[v]) {
    if (vis[w] || w == par) continue;
    if (2 * sz[w] > total)
      return centroid(w, v, total);
  }
  return v;
}

void balanceTree(int v, int par = -1) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  p[v] = par;
  vis[v] = true;
  for (auto &w: edges[v]) {
    if (vis[w]) continue;
    balanceTree(w, v);
  }
}

void lcadfs(int v, int par, int d) {
  lcap[v] = par;
  lcad[v] = d;
  for (auto &w: edges[v]) {
    if (w == par) continue;
    lcadfs(w, v, d+1);
  }
}

void paint(int v) {
  red[v] = true;
  int w = v;
  while (w != -1) {
    int u = lca.query(v, w);
    int cost = lcad[v] + lcad[w] - 2 * lcad[u];
    dist[w] = min(dist[w], cost);
    w = p[w];
  }
}

int query(int v) {
  int ret = INF;
  int w = v;
  while (w != -1) {
    int u = lca.query(v, w);
    int cost = lcad[v] + lcad[w] - 2 * lcad[u];
    ret = min(ret, dist[w] + cost);
    w = p[w];
  }
  return ret;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  REP (i, n-1) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  balanceTree(0);

  fill(dist, dist+n, INF);
  lcadfs(0, -1, 0);
  lca.init(n, lcap, lcad);
  paint(0);
  REP (i, m) {
    int t, x;
    cin >> t >> x;
    --x;
    if (t == 1)
      paint(x);
    else
      cout << query(x) << endl;
  }
  
  return 0;
}

Codeforces Round #372 Digit Tree

問題
木のノードに1-9までの数字が書かれている。
v, w間のパスに含まれるノードの数字をつないで10進数表記の数を作る。その数がMで割り切れるようなv, wのペアの数を求めよ。

解法
uがv, wのLCAとなるような場合のv, wの組み合わせを考える。
v -> u -> wという順序に通るので、v -> uとu -> wの組み合わせを列挙して、2つをつなげるとMで割るようなものを数えればよい。
あとはuをすべてのノードでループしないといけないが、Centroid Decompositionしておくと計算量を抑えることができる。

ソースコード

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

int n;
long long M;
vector<pair<int, int> > edges[100000];
bool vis[100000];
int sz[100000];
map<int, int> upcnt;
long long r1, r2;
long long pw[100000], ipw[100000];

void szdfs(int v, int par = -1) {
  sz[v] = 1;
  for (auto &e: edges[v]) {
    int w = e.first;
    if (w == par || vis[w]) continue;
    szdfs(w, v);
    sz[v] += sz[w];
  }
}

int centroid(int v, int par, int total) {
  REP (i, edges[v].size()) {
    int w = edges[v][i].first;
    if (w == par || vis[w]) continue;
    if (sz[w] * 2 > total)
      return centroid(w, v, total);
  }
  return v;
}

void downdfs(int v, int par, int acc, int d) {
  if (acc == 0) ++r2;
  r1 += upcnt[(M-acc)*ipw[d]%M];
  for (auto &e: edges[v]) {
    int u, w;
    tie(u, w) = e;
    if (u == par || vis[u]) continue;
    downdfs(u, v, (10LL*acc+w)%M, d+1);
  }
}

void updfs(int v, int par, int acc, int d) {
  if (acc == 0) ++r2;
  ++upcnt[acc];
  for (auto &e: edges[v]) {
    int u, w;
    tie(u, w) = e;
    if (u == par || vis[u]) continue;
    updfs(u, v, (acc+pw[d]*w)%M, d+1);
  }
}

void solve(int v) {
  szdfs(v);
  v = centroid(v, -1, sz[v]);
  upcnt.clear();
  REP (i, edges[v].size()) {
    int u = edges[v][i].first;
    int w = edges[v][i].second;
    if (vis[u]) continue;
    downdfs(u, v, w%M, 1);
    updfs(u, v, w%M, 1);
  }

  upcnt.clear();
  REP (i, edges[v].size()) {
    int u = edges[v][edges[v].size()-1-i].first;
    int w = edges[v][edges[v].size()-1-i].second;
    if (vis[u]) continue;
    downdfs(u, v, w%M, 1);
    updfs(u, v, w%M, 1);
  }
  
  vis[v] = true;
  for (auto &e: edges[v]) {
    int w = e.first;
    if (vis[w]) continue;
    solve(w);
  }
}

long long modpow(long long x, long long p, long long mod) {
  long long ret = 1;
  while (p) {
    if (p & 1)
      ret = ret * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ret;
}

long long totient(long long n) {
  long long ret = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      ret = ret / i * (i - 1);
      while (n % i == 0)
        n /= i;
    }
  }
  if (n != 1) 
    ret = ret / n * (n - 1);
  return ret;
}

void init() {
  pw[0] = ipw[0] = 1;
  long long inv = modpow(10, totient(M)-1, M);
  FOR (i, 1, 100000) {
    pw[i] = pw[i-1] * 10 % M;
    ipw[i] = ipw[i-1] * inv % M;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> M;
  REP (i, n-1) {
    int u,v,w;
    cin >> u >> v >> w;
    edges[u].emplace_back(v, w);
    edges[v].emplace_back(u, w);    
  }
  r1 = r2 = 0;
  init();
  solve(0);
  cout << r1 + r2/2 << endl;
  
  return 0;
}

Codeforces Round #121 Div1 C. Fools and Roads

問題

n個の町が道路で結ばれている。グラフ(町, 道路)は木構造になっている。

以下の情報がk個与えられる。

u v

これは、ノードuとノードv間の単純路を人が移動したことを意味する。

各道路について、その道路を通った人の数を求めよ。

解法

u vという情報に対して、以下の処理を実行すればよい。

• uからrootまでのすべての枝に1を足す
• vからrootまでのすべての枝に1を足す
• wからrootまでのすべての枝から2を引く

ただし、wはLCA(u, v)とする。

毎回計算していたら遅いので、情報をすべて集めたあとに、葉から根方向にDPしながら和を計算すればよい。

実装

LCAのライブラリを作っておけば、張ってちょっと足して終わり。

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define ALL(x) (x).begin(), (x).end()

int n;
vector<int> edges[100000];
int par[100000];
int depth[100000];
long long cost[100000];
long long r[100000];
map<pair<int, int>, int> etoi;

class LCA {
  int V, logV;
  vector<int> depth;
  vector<vector<int> > parent;
  
  void build() {
    for (int k = 0; k + 1 < logV; k++) {
      for (int v = 0; v < V; v++) {
        if (parent[k][v] < 0) parent[k+1][v] = -1;
        else parent[k+1][v] = parent[k][parent[k][v]];
      }
    }
  }
public:
  // V: maximum number of nodes
  LCA(int V) {
    this->V = V;
    logV = 0;
    while (V > (1LL<<logV)) logV++;
    this->depth = vector<int>(V);
    this->parent = vector<vector<int> >(logV, vector<int>(V));
  }
  
  // N: number of nodes
  // p: parent of nodes (p[root] = -1)
  // d: depth of nodes (d[root = 0])
  void init(int N, int p[], int d[]) {
    for (int i = 0; i < N; i++) {
      parent[0][i] = p[i];
      depth[i] = d[i];
    }
    this->build();
  }
  
  // p: parent of nodes (p[root] = -1)
  // d: depth of nodes (d[root = 0])
  void init(vector<int> p, vector<int> d) {
    int N = d.size();
    for (int i = 0; i < N; i++) {
      parent[0][i] = p[i];
      depth[i] = d[i];
    }
    this->build();
  }
  
  int query(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    for (int k = 0; k < logV; k++) {
      if ((depth[v] - depth[u]) >> k & 1)
        v = parent[k][v];
    }
    if (u == v) return u;
    
    for (int k = logV-1; k >= 0; k--) {
      if (parent[k][u] != parent[k][v]) {
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }
};

void rec(int v, int p = -1) {
  for (auto w: edges[v]) {
    if (w != p) {
      rec(w, v);
      r[etoi[make_pair(v, w)]] += cost[w];
      cost[v] += cost[w];
    }
  }
}

void dfs(int v, int p = -1, int d = 0) {
  par[v] = p;
  depth[v] = d;
  for (auto &w: edges[v]) {
    if (w != p)
      dfs(w, v, d+1);
  }
}

int main() {
  scanf(" %d", &n);
  REP (i, n-1) {
    int x, y;
    scanf(" %d %d", &x, &y);
    --x, --y;
    etoi[make_pair(x, y)] = i;
    etoi[make_pair(y, x)] = i;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }

  dfs(0);

  LCA lca(100000);
  lca.init(n, par, depth);

  int k;
  scanf(" %d", &k);
  REP (i, k) {
    int x, y;
    scanf(" %d %d", &x, &y);
    --x, --y;
    ++cost[x];
    ++cost[y];
    int z = lca.query(x, y);
    cost[z] -= 2;
  }

  rec(0);
  REP (i, n-1)
    cout << r[i] << " ";
  cout << endl;

  return 0;
}

Codeforces Round #359 (Div. 2) D. Kay and Snowflake

問題概要
ノード数nの木が与えられる。
q個のクエリが飛んでくる。
クエリの入力vに対して、ノードvのcentroidを出力せよ。

解法
自分のすべての子のcentroidが分かっているとする。
すると自分のcentroidは、自分と、最大の部分木を持つ自分の子のパス上にあることが分かる。

実装
dfs1回で書けそうな気もするが、素直に2回に分けて書いた方がよい。

#pragma comment(linker, "/STACK:256000000")

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, q;
vector<int> ch[300000];
int par[300000];
int maxc[300000];
int centroid[300000];
int sz[300000];

void dfs(int v) {
  sz[v] = 1;
  maxc[v] = 0;
  for (auto &w: ch[v]) {
    dfs(w);
    sz[v] += sz[w];
    maxc[v] = max(maxc[v], sz[w]);
  }
}

bool check(int v, int c) {
  return 2 * (sz[v] - sz[c]) <= sz[v] && 2 * maxc[c] <= sz[v];
}

void centroid_dfs(int v) {
  if (!ch[v].size())
    centroid[v] = v;
  else {
    int c = -1;
    for (auto &w: ch[v]) {
      centroid_dfs(w);
      if (sz[w] == maxc[v])
        c = w;
    }
    c = centroid[c];
    while (!check(v, c))
      c = par[c];
    centroid[v] = c;
  }
}

int main() {
  scanf(" %d %d", &n, &q);
  int v;
  REP (i, n-1) {
    scanf(" %d", &v);
    --v;
    par[i+1] = v;
    ch[v].push_back(i+1);
  }
  dfs(0);
  centroid_dfs(0);
  REP (i, q) {
    scanf(" %d", &v);
    printf("%d\n", centroid[--v]+1);
  }
  return 0;
}

Codeforces Round #351 Div2 E. Levels and Regions

問題概要
あなたはテレビゲームをプレーしている。
このゲームでは、1からnまでの階があり、それらはk個の地区に分かれている。
各階iには、対応するトークンがt[i]個ある。

今あなたは地区Xにいるとする。
そのとき、コンピュータによって以下の操作が行われる。

• 袋にX内のクリア済みの階に対応するトークンを入れる。
• 袋にX内のまだクリアしていない最低階に対応するトークンを入れる。
• 袋から一様な確率でランダムにトークンを引く。

あなたは袋から引かれたトークンに対応する階をプレーしないといけない。

一つの階をクリアするには1時間かかる。
各階をどのように地区に振り分けるかは自由である。
すべての階をクリアするために必要なプレー時間の期待値の最小値を求めよ。

解法
(地区を何個まで区切ったか, 階)を状態数としてDPすればいいのはすぐ分かる。
これだけだと遅いので、うまく式変形してConvex Hull Trickを使って高速化する。

実装
ライブラリ化している人が多かったので、自分もライブラリ作ってみた。
処理の詳細な説明は蟻本に載っている。

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++)

const double oo = 1e100;
int n, k;
int ts[200000];
double sum[200000+1];
double rev[200000+1];
double pre[200000+1];
double dp[50+1][200000+1];

template <typename T>
// line f(x) = ax + b
struct line {
  T a, b;
  line() {}
  line(T a, T b) : a(a), b(b) {}
  T eval(T x) { return a * x + b; }
};

template <typename T>
// get min_l {f_l(x)} with convex hull trick
struct CHT {
  int s;
  int t;
  vector<line<T> > deq;

  CHT(int n) {
    deq = vector<line<T> >(n);
    clear();
  }

  void clear() {
    s = t = 0;
  }
  
  bool check(const line<T> &l1, const line<T> &l2, const line<T> &l3) {
    return (l2.a-l1.a) * (l3.b-l2.b) >= (l2.b-l1.b) * (l3.a-l2.a);
  }
  
  void push(T a, T b) {
    line<T> l(a, b);
    while (s + 1 < t && check(deq[t-2], deq[t-1], l))
      --t;
    deq[t++] = l;
  }
  
  
  T get(T x) {
    while (s + 1 < t && deq[s].eval(x) >= deq[s+1].eval(x))
      ++s;
    return deq[s].eval(x);
  }
  
};

void solve() {
  REP (i, n) sum[i+1] = sum[i] + ts[i];
  REP (i, n) rev[i+1] = rev[i] + 1.0 / ts[i];
  REP (i, n) pre[i+1] = pre[i] + sum[i+1] / ts[i];
  REP (i, k+1) REP (j, n+1) dp[i][j] = oo;
  dp[0][0] = 0.0;
  CHT<double> cht(n+1);
  REP (i, k) {
    cht.clear();
    REP (j, n) {
      cht.push(-sum[j], dp[i][j] - pre[j] + rev[j] * sum[j]);
      double tmp = pre[j+1] + cht.get(rev[j+1]);
      dp[i+1][j+1] = min(dp[i+1][j+1], tmp);      
    }
  }
}

int main() {
  scanf(" %d %d", &n, &k);
  REP (i, n) scanf(" %d", ts+i);
  solve();
  printf("%.9lf\n", dp[k][n]);
  return 0;
}

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