Codeforces #349 Div1. A. Reberland Linguistics

レート増のチャンスをまたしょうもないミスで逃した。
http://codeforces.com/contest/666/problem/A

問題

文字列Sを作りたい。
その際、以下のようにして作る。

• まず先頭何文字かを選択する。ただし５文字以降であること。
• その後ろに2文字か3文字の文字列を連結していく。ただし同じ文字列を２回連続して連結してはいけない。

後者の２・３文字の連結文字列としてあり得るものを列挙せよ。

解法

いくつか方法がありそうだが自分はDPでやった。
後ろから、残りx文字をルールに反しない範囲で連結可能か求め、その直前にある２・３文字を候補として挙げていった。

string S;
int L;

int dp[101010][5];
set<string> SS;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	L=S.size();
	dp[L][2]=1;
	for(x=L-2;x>=5;x--) {
		
		if(x+2==L) {
			dp[x][2]=1;
		}
		else if(x+3==L) {
			dp[x][3]=1;
		}
		else {
			if(dp[x+2][2]) {
				if(S[x]!=S[x+2] || S[x+1]!=S[x+3]) dp[x][2]=1;
			}
			if(dp[x+2][3]) dp[x][2]=1;
			if(dp[x+3][2]) dp[x][3]=1;
			if(dp[x+3][3]) {
				if(S[x]!=S[x+3] || S[x+1]!=S[x+4] || S[x+2]!=S[x+5]) dp[x][3]=1;
			}
		}
		if(dp[x][2]) SS.insert(S.substr(x,2));
		if(dp[x][3]) SS.insert(S.substr(x,3));
	}
	cout<<SS.size()<<endl;
	FORR(r,SS) cout<<r<<endl;
}

まとめ

いまいち意図がわからない問題。