TopCoder SRM 698 Div1 Easy RepeatString、Div2 Easy RepeatStringEasy

Easyを簡単に解けたので一応レートは上がった。
https://community.topcoder.com/stat?c=problem_statement&pm=14391
https://community.topcoder.com/stat?c=problem_statement&pm=14390

問題

文字列がSquareであるとは、同じ文字列を２回繰り返した形になっているものを示す。
今文字列Sを、Squareな文字列にしたい。

• Div1 Easy : 1文字の追加・削除・置換を最少何回行えばよいか答えよ。
• Div2 Medium : 1文字の削除を何回か行う場合、最大何文字のSquareな文字列を作れるか答えよ。

解法

S=A+Bと分離したとき、A=Bになるように文字列を編集すればよい。
A,Bの境を総当たりし、以下を求めよう。

• Div1 Easy : 編集距離の最小値
• Div2 Medium : LCSの最大値

int dp[51][51];
class RepeatString {
	public:
	int dodo(string S,string T) {
		int A=S.size(),B=T.size();
		int i,x,y,j;
		FOR(i,51) dp[0][i]=dp[i][0]=i;
		
		for(i=1;i<=A;i++) for(j=1;j<=B;j++) {
			dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);
			dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(S[i-1]!=T[j-1]));
		}
		return dp[A][B];
	}
	
	int minimalModify(string s) {
		int N=s.size();
		
		int ret=101010;
		for(int i=0;i<=N;i++) ret=min(ret,dodo(s.substr(0,i),s.substr(i,N-i)));
		return ret;
		
	}
}

int dp[51][51];
class RepeatStringEasy {
	public:
	
	int dodo(string S,string T) {
		int A=S.size(),B=T.size();
		int i,x,y,j,ret=0;
		ZERO(dp);
		FOR(i,A+1) FOR(j,B+1) {
			if(i<A && j<B) dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+(S[i]==T[j]));
			if(j<B) dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
			if(i<A) dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
			ret=max(ret,dp[i][j]);
		}
		
		return ret;
	}
	
	
	int maximalLength(string s) {
		int N=s.size();
		
		int ret=0;
		for(int i=0;i<=N;i++) ret=max(ret,dodo(s.substr(0,i),s.substr(i,N-i)));
		return ret*2;
		
	}
}

まとめ

編集距離のDP、覚えてなくて調べながら書いた。
覚えてたらもう少し早く解けたな…。