Codeforces #272 Div1 C. Dreamoon and Strings

これは自力で解けた。
http://codeforces.com/contest/477/problem/C

問題

2つの文字列S,Pがある。
文字列Sから任意の文字をx個取り除いたとき、S中に含まれる連続かつ重複しないPの最大数をans(x)とする。
0≦x≦|S|の各xに対し、ans(x)を答えよ。

解法

Sの1文字毎にDPで処理していく。
DP[Sの文字位置][Pとマッチした文字数]を状態とし、その状態に至る文字削除回数の最小値・最大値を更新していく。

DP[i][j]に対し：

• S[i]==P[j]ならPのマッチ数を1増やせるので、削除回数を増やさずDP[i+1][j+1]をDP[i][j]で更新する。
• S[i]!=P[j]ならPのマッチ数を1増やせるので：
  • j%|P|==0の場合、現在位置はPの最中ではないため文字を削除してもマッチングに影響しないので、D[i+1][j]をDP[i][j]で更新する。
  • それ以外の場合、文字を削除しないとマッチングが成立しないのでD[i+1][j]をDP[i][j]+1で更新する。(j%|P|==0も削除してもよい)

これでDP[i][j]を求めると、(DP[i][j]の最小値)≦x≦(DP[i][j]の最小値)となる各削除数xに対し、ans(x)をj/|P|で更新していく。

DPパートもansを求めるパートもO(|S|^2)。

string S,P;
int LS,LP;
int dpdp[2002][2002][2];
int res[2002];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>P;
	LS=S.size();
	LP=P.size();
	
	MINUS(dpdp);
	FOR(i,LS+1) FOR(j,LS+1) dpdp[i][j][0]=3000;
	FOR(i,LS+1) FOR(j,LS+1) dpdp[i][j][1]=-1;
	
	dpdp[0][0][0]=dpdp[0][0][1]=0;
	
	FOR(i,LS) FOR(j,LS) if(dpdp[i][j][1]>=0) {
		if(S[i]==P[j%LP]) {
			dpdp[i+1][j+1][0]=min(dpdp[i+1][j+1][0],dpdp[i][j][0]);
			dpdp[i+1][j+1][1]=max(dpdp[i+1][j+1][1],dpdp[i][j][1]);
		}
		if((j%LP)==0) dpdp[i+1][j][0]=min(dpdp[i+1][j][0],dpdp[i][j][0]);
		dpdp[i+1][j][0]=min(dpdp[i+1][j][0],dpdp[i][j][0]+1);
		dpdp[i+1][j][1]=max(dpdp[i+1][j][1],dpdp[i][j][1]+1);
	}
	FOR(i,LS+1) if(dpdp[LS][i][1]>=0) {
		for(j=dpdp[LS][i][0];j<=dpdp[LS][i][1];j++) res[j]=max(res[j],i/LP);
	}
	FOR(i,LS+1) _P("%d ",res[i]);
	_P("\n");
}

まとめ

人によってDPのやり方が色々ありそうな問題。