九州大学プログラミングコンテスト2018 : J - Repeat Strings

これは思いつかなかった…。
https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_j

問題

abで構成される文字列Sが与えられる。
以下のクエリに順次答えよ。

各クエリはやはりabで構成された文字列Tが与えられる。
Tを繰り返した物の|S|文字分のprefixをT'とする。
Sのうち、連続区間を指定してab反転する、という処理を繰り返しSをT'にするための最小処理回数を答えよ。

解法

文字列abを01のbit列とみなす。
また、以下のようにbit列を変換しよう。これは文字間の差分を取った列である。

• 先頭bitは元のbit列と同じ
• 2bit目以降は、元の文字列で直前のbitと一致するなら0、しないなら1

元の文字列区間を01反転するということは、変換後の文字列に対し２か所01反転することと同じである。
よって、返還後の文字列においてSとT'で異なるbitがn個あれば、ceil(n/2)が必要最小反転数である。

もう一つやることがある。
各クエリを、|T|の大きさで分類し、同じ大きさのものをまとめて扱おう。
S[i]とT[i%|T|]が等しいかどうか何度も判定することになるので、先にS[i]を|T|毎に分割して、各位置の01の登場回数をカウントしておくと、SとTの01不一致判定が前処理はO(|S|)だがクエリ毎にO(|T|)で済む。

T

の種類はそんなにないので、前処理の回数はO(√sum(

T

))程度に抑えられる。

int N,Q;
string S;
string T[202020];
vector<int> V[202020];
int ret[202020];

int num[202020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	cin>>Q;
	FOR(i,Q) {
		cin>>T[i];
		if(T[i].size()>N) T[i].resize(N);
		V[T[i].size()].push_back(i);
	}
	
	for(i=1;i<=N;i++) if(V[i].size()) {
		
		for(j=1;j<N;j++) num[j%i][S[j]!=S[j-1]]++;
		
		FORR(v,V[i]) {
			FOR(j,i) ret[v]+=num[(j+1)%i][T[v][j]==T[v][(j+1)%i]];
			ret[v]+=S[0]!=T[v][0];
			ret[v]=(ret[v]+1)/2;
		}
		
		FOR(j,i) num[j][0]=num[j][1]=0;
	}
	
	FOR(i,Q) cout<<ret[i]<<endl;
}

まとめ

このタイプの平方分割、よく忘れる。