レート増のチャンスをまたしょうもないミスで逃した。
http://codeforces.com/contest/666/problem/A
問題
文字列Sを作りたい。
その際、以下のようにして作る。
- まず先頭何文字かを選択する。ただし5文字以降であること。
- その後ろに2文字か3文字の文字列を連結していく。ただし同じ文字列を2回連続して連結してはいけない。
後者の2・3文字の連結文字列としてあり得るものを列挙せよ。
解法
いくつか方法がありそうだが自分はDPでやった。
後ろから、残りx文字をルールに反しない範囲で連結可能か求め、その直前にある2・3文字を候補として挙げていった。
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; }
まとめ
いまいち意図がわからない問題。