Hatena::Grouptopcoder

kuuso1の日記

2016-05-06

CodeForces Round#350 Div2 E. Correct Bracket Sequence Editor

| 18:49 | CodeForces Round#350 Div2 E. Correct Bracket Sequence Editor - kuuso1の日記 を含むブックマーク はてなブックマーク - CodeForces Round#350 Div2 E. Correct Bracket Sequence Editor - kuuso1の日記

http://codeforces.com/contest/670/problem/E

  • 正しく対応の付いたかっこからなる文字列(correct bracket sequences (CBS))と、CBS-editorの操作が与えられる。
  • CBS-editorは以下をサポートする
    • D:カーソル位置に対し対応するかっこをみつけて、そのかっこに挟まれる文字列をすべてDeleteする。カーソルは消去後に右隣(文字が無い場合は左隣)に移動。
    • L:カーソルを一つ左に移動させる
    • R:カーソルを一つ右に移動させる
  • 与えられたCBSおよびCBS-editorの操作の後に残る文字列を答えよ

(制約)1 ≤ 文字列長 N ≤ 5*10^5, 1 ≤ 操作数 M ≤ 5*10^5,

・愚直に実装すると、文字列を都度つくりなおすとdeleteが最悪O(MN)に、作り直さない場合は移動とdeleteが最悪O(MN)となる。

・まず対応するかっこの位置を求めておく。これはスタックを使えば出来る。

f:id:kuuso1:20160506183136p:image

・Deleteはその部分を以降スキップすることだと考えれば、カーソルがそのdelete位置に乗った場合は対応するかっこまで強制的に移動することとみなすことが出来る。

・なので、deleteされた部分をUnionFindで管理する。これでDeleteは高々ならしO(log(N))程度の計算で済む。

・移動については、このままだとdeleteされたブロックがたくさん並んでいる場合にそのブロック数だけ進む必要がでてしまうので、deleteした際に隣接文字がすでにdeleteされている場合はマージしておく。これで移動も高々ならしO(log(N))の計算で済む。

Uniteの際にかっこの左端/右端を持たせておく。

f:id:kuuso1:20160506184432p:image

・※Uniteと左端/右端クエリは計算量を高々ならしO(log(N))と見積もってます(Parent(*)が親の付け替えだけだけなので)。

・最終的にdeleteされていない部分を出力する。この時、delete部分に含まれているかっこのなかには全くアクセスされていない文字もあるため、いもす法で被覆回数を計算する。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol  = new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		Stack<int> Stk = new Stack<int>();
		int idx = 0;
		int[] L = new int[N/2];
		int[] R = new int[N/2];
		int[] LR = new int[N];
		for(int i = 0;i<N;i++){
			if(S[i] == '('){
				Stk.Push(idx);
				L[idx] = i;
				LR[i] = idx;
				idx++;
			}else{
				var jdx = Stk.Pop();
				R[jdx] = i;
				LR[i] = jdx;
			}
		}
		
		var UF = new UnionFind(N);
		
		int cur = P-1;
		for(int t = 0;t<M;t++){
			switch(Ord[t]){
				case 'D':
					int l = 0,r = 0;
					if(S[cur] == '('){
						l = cur;
						r = R[LR[cur]];
					}else{
						r = cur;
						l = L[LR[cur]];
					}
					UF.Unite(l,r);
					if(r+1<N && UF.MemCnt(r+1) != 1){
						UF.Unite(r,r+1);
					}
					if(l-1>=0 && UF.MemCnt(l-1) != 1 ){
						UF.Unite(l-1,l);
					}
					
					l = UF.Left(l);
					r = UF.Right(r);
					if(r+1<N){
						cur = r+1;
					}else{
						cur = l-1;
					}
				break;
				case 'L':
					if(UF.Right(cur-1) == UF.Left(cur-1)){
						cur--;
					}else{
						cur = UF.Left(cur-1)-1;
					}
				break;
				case 'R':
					if(UF.Right(cur+1) == UF.Left(cur+1)){
						cur++;
					}else{
						cur = UF.Right(cur+1)+1;
					}
				break;
			}
		}
		
		
		int[] imos = new int[N+1];
		for(int i = 0;i<N;i++){
			if(UF.isRoot(i)){
				if(UF.MemCnt(i) == 1)continue;
				imos[UF.Left(i)]++;
				imos[UF.Right(i)+1]--;
			}
		}
		int[] sum = new int[N];
		sum[0] = imos[0];
		for(int i = 1;i<N;i++){
			sum[i] = sum[i-1]+imos[i];
		}
		
		List<char> LL = new List<char>();
		for(int i = 0;i<N;i++){
			if(sum[i] == 0){
				LL.Add(S[i]);
			}
		}
		
		Console.WriteLine(new String(LL.ToArray()));
		
	}
	int N,M,P;
	String S;
	String Ord;
	public Sol(){
		var d = ria();
		N = d[0];M = d[1];P = d[2];
		S = rs();
		Ord = rs();
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep = ' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep = ' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e =>int.Parse(e));}
	static long[] rla(char sep = ' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e =>long.Parse(e));}
	static double[] rda(char sep = ' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e =>double.Parse(e));}
}

class UnionFind{
	
	int[] parent;
	int[] mem;
	int compo;
	int N;
	int[] L,R;
	
	public UnionFind(int n_){
		Initialize(n_);
	}
	
	public void Initialize(int n_){
		N = n_;
		parent = new int[N];
		mem = new int[N];
		L = new int[N];
		R = new int[N];
		for(int i = 0;i<N;i++){
			parent[i] = i;
			mem[i] = 1;
			L[i] = i;
			R[i] = i;
		}
		compo = N;
	}
	
	public int Parent(int a){
		if(parent[a] == a)return a;
		return parent[a] = Parent(parent[a]);
	}
	
	public bool areSameGp(int a,int b){
		return Parent(a) == Parent(b);
	}
	
	public void Unite(int a,int b){
		a = Parent(a);b = Parent(b);
		if(a == b)return;
		parent[a] = b;
		mem[b] += mem[a];
		compo -= 1;
		int ll = Math.Min(L[a],L[b]);
		int rr = Math.Max(R[a],R[b]);
		L[b] = L[a] = ll;
		R[b] = R[a] = rr ;
	}
	
	public bool isRoot(int x){
		return x == parent[x];
	}
	public int MemCnt(int x){
		return mem[Parent(x)];
	}
	public int Left(int x){
		return L[Parent(x)];
	}
	public int Right(int x){
		return R[Parent(x)];
	}
	
	public void Dump(){
		for(int i = 0;i<parent.Length;i++){
			Console.Write(i == 0?"{0}":" {0}",parent[i]);
		}
		Console.WriteLine("");
	}
	
	public int Compo{
		get{
			return compo;
		}
	}
}

本番は10数秒間に合わなかったのが残念。

UnionFindに値を持たせるテクは好きなので日記に書いておくことにしました。