Codeforces ECR #089 : G. Construct the String

ECRの最終問題にしては実装が軽め。
https://codeforces.com/contest/1366/problem/G

問題

文字列S,Tが与えられる。Sはアルファベット小文字とピリオドで構成される。
Sの部分列S'に対し、f(S')を以下のように定める。

初期値が空文字である文字列Rを考える。
S'の文字cを端から順に処理し、

• cがアルファベットならRの末尾に追加
• cがピリオドなら、Rの末尾の文字を削除

として、f(S')は最終的に得られたRとする。

f(S')=TとなるようなS'を構築する際Sから削除すべき文字数は最小何文字か。

解法

dp(a,b) := Sの先頭a文字の部分列から、Tの先頭b文字を作れる場合のSから削除すべき文字の最小値
とする。dp(|S|,|T|)=0から初めて、解dp(0,0)を求めよう。

dp(a,b)からの遷移先は以下のうち最小値。

• S[a]を削除する。dp(a,b) := 1+dp(a+1,b)
• S[a]=T[b]なら、S[a]は残す。dp(a,b) := dp(a+1,b+1)
• S[a]='.'ならdp(a,b) := dp(a+1,b-1)
• S[a]!=T[b]でかつS[a]を削除しない場合、のちのピリオドで消さなければならない。
  • S[a]を消してくれるようなS[a...x]となる最小のxを考えると、dp(a,b) := dp(x,b)

string S,T;
int N,M;
int nex[101010];
int memo[10101][10101];
map<int,int> mm;

int hoge(int A,int B) {
	if(memo[A][B]>=0) return memo[A][B];
	
	if(A==N) {
		if(B==M) return 0;
		return 1<<30;
	}
	
	int ret=1+hoge(A+1,B);
	if(B<M && S[A]==T[B]) ret=min(ret,hoge(A+1,B+1));
	if(S[A]=='.' && B) ret=min(ret,hoge(A+1,B-1));
	if(S[A]!='.' && nex[A]!=-1) ret=min(ret,hoge(nex[A],B));
	
	return memo[A][B]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	N=S.size();
	M=T.size();
	
	mm[0]=N;
	int cur=0;
	for(i=N-1;i>=0;i--) {
		if(S[i]=='.') cur--;
		else cur++;
		if(mm.count(cur)) nex[i]=mm[cur];
		else nex[i]=-1;
		mm[cur]=i;
	}
	MINUS(memo);
	cout<<hoge(0,0)<<endl;
	
	
}

まとめ

これTL4秒にするなら、|S|を5000位にすればいいのに…。