kmjp's blog

競技プログラミング参加記です

Google Code Jam 2019 Qualification Round : D. Dat Bae

そういやinteractive問題も出るんだったな。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051705/00000000000881de

問題

N個の機械が並んでおり、うちB個が壊れている。
N,Bは与えられるが、どのB個が壊れているかは不明である。

0/1で構成されたN文字の文字列をクエリとして投げると、各機械は受け取った文字をそのまま返す。
ただし壊れたB個の機械は文字を返さず、クエリの結果はその分の文字を詰めた(N-B)文字として返ってくる。

クエリをF回まで用いて、壊れた機械を特定せよ。

解法

機械の台数を1024台と固定させるとラクである。
(N+1)~1024台目には壊れたものはないと考え、クエリとその結果を補うとよい。

Visible (F=10)

Nの上限が1024なので、二分探索で求めよう。
f(L,R) := [L,R)のうち壊れた機械の数
とする。初期状態はf(0,N)=Bであり、f(i,i+1)を全部求められれば良い。

f(L,R)がわかっているならば、M=(L+R)/2に対し、クエリの[L,M)文字目に0、[M,R)文字目に1を入れれば、その返り値に0,1が何個あるかによってf(L,M)とf(M,R)が求められる。
10回行えばf(i,i+1)が求められる。

Hidden (F=5)

Bが15以下というのがミソである。
初手で、01を16文字ごとに切り替えたクエリを投げよう。
そうするとf(0,16),f(16,32), f(32,48),....が求められる。
あとは上記二分探索を4回行えばよい。

以下では二分探索の代わりに、0/1を1,2,4,8毎に切り替えた場合の文字列を先に持っておいて、合致するものを選ぶということをしているが本質的には二分探索と同じ。

int N,B,F;

string C[5];
string R[5];
string cand[1<<16][4];
int num[1024/16];
int rmask[1024/16];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>B>>F;
	FOR(i,5) {
		cout<<C[i].substr(0,N)<<endl;
		cin>>R[i];
		R[i]+=C[i].substr(N);
	}
	ZERO(num);
	
	int cur=-1;
	int p=-1;
	FORR(r,R[4]) {
		if(r!=p) cur++;
		p=r;
		num[cur]++;
	}
	
	cur=0;
	FOR(i,1024/16) {
		rmask[i]=-1;
		for(int mask=0;mask<1<<16;mask++) if(__builtin_popcount(mask)==num[i]) {
			int ok=1;
			FOR(j,4) if(cand[mask][j]!=R[j].substr(cur,num[i])) ok=0;
			if(ok) rmask[i]=mask;
		}
		assert(rmask[i]!=-1);
		
		cur+=num[i];
	}
	
	vector<int> ret;
	
	FOR(i,N) {
		if((rmask[i/16]&(1<<(i%16)))==0) ret.push_back(i);
	}
	FOR(i,ret.size()) {
		cout<<ret[i];
		if(i==ret.size()-1) cout<<endl;
		else cout<<" ";
	}
	
	cin>>x;
	assert(x==1);
	
	
}

void init() {
	int i,j,mask;
	FOR(i,5) {
		FOR(j,1024) C[i].push_back('0'+(j/(1<<i))%2);
	}
	FOR(mask,1<<16) {
		FOR(j,16) if(mask&(1<<j)) {
			FOR(i,4) {
				cand[mask][i].push_back('0'+(j/(1<<i))%2);
			}
		}
	}
	
}

int main(int argc,char** argv){
	int loop,loops;
	long long span;
	char tmpline[1000];
	struct timeval start,end,ts;
	
	if(argc>1) freopen(argv[1], "r", stdin);
	gettimeofday(&ts,NULL);
	cin>>loops;
	init();
	for(loop=1;loop<=loops;loop++) {
		gettimeofday(&start,NULL); solve(loop); gettimeofday(&end,NULL);
		span = (end.tv_sec - start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
	}
	
	start = ts;
	span = (end.tv_sec - start.tv_sec)*1000000LL + (end.tv_usec - start.tv_usec);
	fprintf(stderr,"**Total time: %lld ms\n",span/1000);
	
	return 0;
}

まとめ

Small\Large、ではないんだな。