Codeforces #873 : Div1 C. Palindrome Partition

意外と過去に出てないんだな。
https://codeforces.com/contest/1827/problem/C

問題

文字列Sが与えられる。
Sの部分文字列のうち、偶数長の回文を連結してできるものは何通りか。

解法

ある文字列が偶数長の回文を連結してできる場合、その分割位置は先頭からどん欲に偶数長に回文を取り除いていくことができる。

f(n) := S[n-1]を末尾とする条件を満たす文字列の数
g(n) := S[n]を先頭とする偶数長の回文のうち最短の長さ
とすると、f(n+g(n)) = 1+f(n)
というように状態遷移できるので、Manacherを実行後DPでf(n)を求めて行こう。

int T,N;
string S;
int R[502020];
vector<int> add[502020];
ll dp[502020];

pair<vector<int>,pair<int,int> > manacher(string S) {
	int L=S.size(),i,j,k;
	vector<int> rad(2*L-1,0);
	for(i=j=0;i<2*L-1;i+=k,j=max(j-k,0)) {
		while(i-j>=0 && i+j+1<=2*L-1 && S[(i-j)/2]==S[(i+j+1)/2]) j++;
		rad[i]=j;
		for(k=1;i-k>=0 && rad[i]-k>=0 && rad[i-k]!=rad[i]-k&&i+k<rad.size(); k++) rad[i+k]=min(rad[i-k],rad[i]-k);
	}
	i=max_element(rad.begin(),rad.end())-rad.begin();
	return make_pair(rad,make_pair((i-(rad[i]-1))/2,(i+(rad[i]-1))/2));
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		auto V=manacher(S).first;
		FOR(i,N+1) R[i]=1<<30, dp[i]=1,add[i].clear();
		for(i=1;i<V.size();i+=2) if(V[i]) {
			x=i/2+1-V[i]/2;
			add[x].push_back(V[i]+2*x);
		}
		ll ret=0;
		priority_queue<int, vector<int>, greater<int> > Q;
		FOR(i,N) {
			FORR(a,add[i]) Q.push(a);
			while(Q.size()&&Q.top()-2*i<=0) Q.pop();
			if(Q.size()) {
				x=Q.top()-2*i;
				ret+=dp[i];
				dp[i+x]+=dp[i];
			}
		}
		
		cout<<ret<<endl;
	}
}

まとめ

久々にmanacher使ったかも。