Codeforces LATOKEN Round 1 : E. Lost Array

これはどうにか通せた。
https://codeforces.com/contest/1534/problem/E

問題

N要素の整数列Aがあるが、その中身は不明である。
この全要素のxorの値を求めたい。

その際、以下のクエリを用いることができる。

• A中ちょうどK個の要素を指定し、それらのxorを答える。

最小のクエリ回数で、上記値を求めよ。

解法

メモ化再帰なりDPなりで以下を求めよう。
f(n) := 残りn要素のxorを求めるのに、クエリ何回かかるか。
g(n) := 残りn要素のxorを求めるのに、クエリf(n)回で済ませるには、n要素中から何要素選べばよいか。
なお、次のクエリはn要素の中から要素を選んでも良いし、それ以外の(N-n)要素の中から選んでも良い。
そのパターンを事前に網羅していこう。

あとはg(*)に従い要素を選んでいこう。

int N,K;

int num[505];
int from[505];


int ask(vector<int> V) {
	assert(V.size()==K);
	cout<<"?";
	FORR(v,V) cout<<" "<<v+1;
	cout<<endl;
	int i;
	cin>>i;
	return i;
}
void ans(int v) {
	cout<<"! "<<v<<endl;
	exit(0);
}

int dfs(int cur) {
	if(num[cur]>=0) return num[cur];
	num[cur]=1010;
	int lef=N-cur;
	for(int x=0;x<=K;x++) {
		int y=K-x;
		if(x>cur) continue;
		if(y>lef) continue;
		int r=dfs(cur-x+y);
		if(r<num[cur]) {
			num[cur]=r;
			from[cur]=x;
		}
	}
	
	num[cur]++;
	return num[cur];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	MINUS(num);
	num[0]=0;
	x=dfs(N);
	if(x>N) {
		cout<<-1<<endl;
		return;
	}
	int ret=0;
	int cur=N;
	set<int> S,T;
	FOR(i,N) S.insert(i);
	while(cur!=0) {
		x=from[cur];
		y=K-x;
		vector<int> A,V,W;
		FOR(i,x) {
			A.push_back(*S.begin());
			V.push_back(*S.begin());
			S.erase(S.begin());
		}
		FOR(i,y) {
			A.push_back(*T.begin());
			W.push_back(*T.begin());
			T.erase(T.begin());
		}
		FORR(v,V) T.insert(v);
		FORR(v,W) S.insert(v);
		ret^=ask(A);
		
		cur=cur-x+y;
	}
	ans(ret);
	
}

まとめ

一見最小手数を要求されて戸惑うが、よく見ると難しくない問題。