Codeforces #1022 : Div2 D. Needle in a Numstack

割といい結果だった。
https://codeforces.com/contest/2108/problem/D

問題

インタラクティブ問題である。
整数N,Kが与えられる。
2つの整数列A,Bがあり、以下を満たす。

• どちらも要素数がK個以上
• どちらも連続するK要素を取ると、異なる値がある。

C=A+Bとする。
Cのうち最大250要素まで値を得られるとき、AとBの長さを特定せよ。

解法

A,Bはいずれも周期Kのパターンを繰り返した形になる。
よって、A,Bは実質長さKだけ考える。
f(n) := n%K
g(n) := C[n]がもしBの一部である場合、C[n]=B[m]となるようなm

とする。A[f(n)]!=B[g(n)]となるf(n),g(n)を求め、それをlとする。
l+a*Kの形の添え字に対し、C[l+a*K]=A[f(n)]となるはずだが、途中からB[g(n)]となるはずである。
C[l+a*K]=A[f(n)]となる最大のaを考えると、|A|は(l+a*K+1)～(l+(a+1)*K)のいずれかなので、総当たりしていこう。

int T,N,K;
int A[55],B[55];

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,K) A[i]=ask(i);
		FOR(i,K) B[(N-1-i)%K]=ask(N-1-i);
		
		if(2*K==N) {
			cout<<"! "<<K<<" "<<K<<endl;
			continue;
		}
		
		x=-1;
		FOR(i,K) if(A[i]!=B[i]) x=i;
		if(x==-1) {
			cout<<"! -1"<<endl;
			continue;
		}
		int L=x,R=x;
		while(R+K<N) R+=K;
		while(L+K<R) {
			int M=L+(R-L)/K/2*K;
			y=ask(M);
			if(y==A[x]) {
				L=M;
			}
			else {
				R=M;
			}
		}
		map<int,int> V;
		V[L]=1;
		V[R]=2;
		for(i=L+1;i<R;i++) {
			y=ask(i);
			k=0;
			if(y==A[i%K]) k|=1;
			if(y==B[i%K]) k|=2;
			if(i<K) k=1;
			if(i>=N-K) k=2;
			V[i]=k;
		}
		int fix=-1;
		for(i=L;i<R;i++) {
			if(V[i]==1&&V[i+1]==2) {
				fix=i+1;
				break;
			}
		}
		
		if(fix==-1) {
			cout<<"! -1"<<endl;
		}
		else {
			cout<<"! "<<fix<<" "<<(N-fix)<<endl;
		}
		
		
	}
}

まとめ

いまいち何がしたいかわからない問題だった。