CSAcademy Round #29 : D. Odd Palindromes

苦戦したけど一応全完。
https://csacademy.com/contest/round-29/task/odd-palindromes/

問題

N文字の文字列Sが与えられる。
このうちK文字を書き換えられるとする。

Sの部分文字列のうち、さらにその奇数長の部分文字列が必ず回文であるようなものを求めよ。

解法

部分文字列の先頭を総当たりS[L]しながら、終端S[R]を尺取り法の要領で求めていく。
奇数長の部分文字列が必ず回文であるためには、2文字が交互に登場するような文字列であればよい。

S[L..R]に対し、終端をS[L..(R+1)]に伸ばせるかどうか判定するためには、奇数文字目と偶数文字目に登場する文字をそれぞれ数えておき、K文字以下の変更で奇数文字目と偶数文字目の文字をすべて一致可能かどうか計算すればよい。
アルファベットの種類をσとするとO(Nσ)で解ける。

int N,K;
string S;

int cnt[256][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>S;
	N=S.size();
	FORR(c,S) c-='a';
	
	int ma=0;
	x=0;
	FOR(i,N) {
		while(x<N) {
			int ma[2]={},sum[2]={};
			cnt[S[x]][x%2]++;
			FOR(j,26) sum[0]+=cnt[j][0], ma[0]=max(ma[0],cnt[j][0]);
			FOR(j,26) sum[1]+=cnt[j][1], ma[1]=max(ma[1],cnt[j][1]);
			int dif=max(0,sum[0]-ma[0])+max(0,sum[1]-ma[1]);
			if(dif>K) {
				cnt[S[x]][x%2]--;
				break;
			}
			x++;
		}
		ma=max(ma,x-i);
		
		cnt[S[i]][i%2]--;
	}
	cout<<ma<<endl;
	
}

まとめ

これは解法が思いつけてよかったね。