Codeforces #897 : Div2 E2. Salyg1n and Array (hard version)

コードは短い。
https://codeforces.com/contest/1867/problem/E2

問題

整数NとKが与えられる。
N,Kは偶数である。
N要素の整数列Aに対し、そのxorを求めるinteractive問題である。

1回のクエリで、連続K要素のxorを求められる。ただし、その後そのK要素が反転する。
これらをうまく使い、Aのxorを求めよ。

解法

初手でA[0...(K-1)]、次にA[(N%K)/2....((N%K)/2+K-1]に対しクエリを投げ、そのxorを取ろう。
すると先頭N%K要素のxorを取った状態となる。
あとはKの倍数長個の要素がのこってるので、K個ずつクエリでxorを求めればよい。

int T;
int N,K;

int ask(int v) {
	int ret;
	cout<<"? "<<v+1<<endl;
	cin>>ret;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ll ret=0;
		
		if(N%K) {
			ret^=ask(0);
			ret^=ask((N%K)/2);
		}
		for(i=N%K;i<N;i+=K) ret^=ask(i);
		cout<<"! "<<ret<<endl;
	}
}

まとめ

この解法シンプルでいいな。