Codeforces #885 : Div2 F. Vika and Wiki

ボス問にしては割とあっさり。
https://codeforces.com/contest/1848/problem/F

問題

N(2の累乗)要素の整数列Aが与えられる。
A[i]=A[i] xor A[(i+1)%N]
という処理を全要素に一斉に行うことを考える。
何度か行うとAはすべて0になる。何回行えばよいか。

解法

Aの1bit分がどれだけ他の要素に影響するかを考える。
2^m回処理を行うと、A[i]に立っているbitはA[i-(2^m)]にも立つ。

そこで2^m回処理を一気に進めてみて、Aが0になるなら解は2^m以下なので、巻き戻して2^(m-1)解処理を進めるのを試す。
まだ0にならないなら、再度2^m回処理を行う。
というのをmの大きい順に試してみるとよい。

int N;
int A[1<<20];
int B[3<<20];
int C[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
	}
	
	FOR(i,N) if(A[i]) break;
	if(i==N) {
		cout<<0<<endl;
		return;
	}
	
	
	int step=0;
	for(i=N;i>=2;i/=2) {
		FOR(k,2) {
			FOR(j,N*2) {
				B[j+1]=B[j]^A[j%N];
			}
			FOR(j,N) C[j]=B[j+i]^B[j];
			FOR(j,N) if(C[j]) break;
			if(j!=N) {
				step+=i-1;
				FOR(j,N) A[j]=C[j];
			}
		}
	}
	
	cout<<step+1<<endl;
}

まとめ

無事思いつけて良かったな。