Codeforces #311 Div2 E. Ann and Half-Palindrome

苦戦したけど解けて良かった。
http://codeforces.com/contest/557/problem/E

問題

文字列Tが半回文であるというのは、前半奇数番目の文字の部分が回文になっている物をいう。
1-indexでいうと、|T|/2以下の奇数iに対しT[i]==T[|T|+1-i]であるものをいう。

abの2種類の文字で構成されたN文字の文字列Sがある。
Sの連続部分文字列のうち半回文となるものをすべて辞書順に並べた場合、K番目に来る文字列を答えよ。
なお、同じ文字列でも抜き出した位置が異なる連続部分文字列は別々にカウントする。

解法

まずどの部分列が半回文であるかを求めよう。
L文字の文字列が半回文であるためには、先頭２文字末尾２文字を除いた文字列がすでに半回分で、かつ先頭と末尾の文字が一致すればよい。
これは簡単なDPでO(N^2)で解ける。

あとは辞書順K番目を求めるだけである。
これは１文字目から順に文字列終了・'a'・'b'のどれが来るかカウントしていけば良い。
i文字目を決める場合、各xについてS[x...x+j] (j≧i)が半回文となるものの数を求める。
その際S[x+i]の文字から、i文字目が文字列終了・'a'・'b'になるケースの数がカウントできる。

K番目がそのうちどこに来るかわかれば、i文字目で文字列終了・'a'・'b'のどれを取ればよいかが判明する。
このように1文字ずつ決めていけば、この処理もO(N^2)で完了できる。

string S;
int L,K;
char ispar[5050][5050];
string res;
deque<int> D[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	L=S.size();
	for(int len=0;len<L;len++) {
		FOR(x,L) if(x+len<L) {
			if(S[x]==S[x+len] && (len<=3 || ispar[x+2][x+len-2])) ispar[x][x+len]=1, D[x].push_back(x+len);
		}
	}
	
	FOR(i,L) {
		int fin=0,a=0,b=0;
		FOR(x,L) if(D[x].size()) {
			if(D[x][0]==x+i-1) fin++,D[x].pop_front();
			if(D[x].empty()) continue;
			if(S[x+i]=='a') a+=D[x].size();
			else b+=D[x].size();
		}
		if(K<=fin) break;
		K-=fin;
		if(K<=a) {
			res+="a";
			FOR(x,L) if(D[x].size() && S[x+i]=='b') D[x].clear();
		}
		else {
			K-=a;
			res+="b";
			FOR(x,L) if(D[x].size() && S[x+i]=='a') D[x].clear();
		}
	}
	
	cout<<res<<endl;
}

まとめ

これ半回文じゃなく回文でもよさそうだったけど。