Codeforces #616 Div1 D. Coffee Varieties (hard version)

こちらはコードは短い。
http://codeforces.com/contest/1290/problem/D

問題

N要素の数列Aがある。
また、パラメータとして2の累乗であるKがある。

以下のクエリを使い、Aのうちdistinctな値が何通りあるかを当てよ。

• 添え字cを指定すると、A[c]が過去K回のクエリ内容と一致するかどうかを答えてくれる
• 過去のクエリをすべて忘れる

解法

クエリを繰り返し、「一致する」と判定された頂点は捨てるということを考える。
すべての2要素対が距離K内でクエリに現れる、という状況を再現すればよい。

s→s-1→s+1→s-2→s+2→…とジグザグに選択するのを、開始位置sをずらしながら行うとよい。
自分自身と一致してしまわないよう、1周したらリセットを掛ける。

int N,K;
int dead[2020];
int vis[2020];
int cnt;
void ask(int v) {
	if(dead[v]) return;
	cout<<"? "<<(v+1)<<endl;
	string S;
	cin>>S;
	if(S=="Y") dead[v]=1;
}
void reset() {
	cout<<"R"<<endl;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	FOR(i,N/K) {
		reset();
		int cur=i;
		FOR(x,N/K) {
			FOR(y,K) ask(cur*K+y);
			
			if(x%2==0) cur=(i+x/2+1)%(N/K);
			else cur=(i-x/2+N/K-1)%(N/K);
		}
		
	}
	
	
	cout<<"! "<<count(dead,dead+N,0)<<endl;
}

まとめ

これすんなり自力で思いつく気がしないな。