CODE FESTIVAL 2015 あさプロ Middle : B - ヘイホー君と削除

これは同時開催のオープンなかったのね。解説も未だになし…？
http://code-festival-2015-morning-middle.contest.atcoder.jp/tasks/cf_2015_morning_easy_d

問題

文字列Sが与えられる。
幾つかの文字を削除し、Sを同じ単語を2回繰り返した形にしたい。
最小何文字削除すればよいか。

解法

Sを前と後ろに二分割する。
分割位置を総当たりし、前と後ろのLCSを取ろう。
最長のLCSが分かれば、それ以外の文字を消せばよいだけ。

int L;
string S;

// 前から検索
int dpdp[111][111];
int lcs(string& AA,string& BB) {
	int x,y,ma=0;
	ZERO(dpdp);
	
	FOR(x,AA.size()) FOR(y,BB.size()) {
		if(AA[x]==BB[y]) dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y]+1);
		dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x][y+1]);
		dpdp[x+1][y+1]=max(dpdp[x+1][y+1],dpdp[x+1][y]);
		ma=max(ma,dpdp[x+1][y+1]);
	}
	return ma;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>L>>S;
	int mi=L;
	for(x=1;x<=L-1;x++) {
		string a=S.substr(0,x), b=S.substr(x);
		mi=min(mi, L-2*lcs(a,b));
	}
	cout<<mi<<endl;
	
}

まとめ

計算量間に合うか心配だったけど、O(|S|^3)だから余裕か。