kmjp's blog

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

Google Code Jam 2019 Round 1C : B. Power Arrangers

このInteractiveも1A/1Bより迷う要素少ない気が。
https://codingcompetitions.withgoogle.com/codejam/round/00000000000516b9/0000000000134e91

問題

ABCDEの5文字の並びは5!=120通りある。
このうち119個を選び、ランダムに並べた後連結して595文字の文字列を作った。
595文字中150か所まで、位置を指定し文字を取得できる場合、120個中選ばれなかった1個を特定せよ。

解法

上の文字から絞っていく。
119個分の1文字目を調べると、ABCDEのうち4つは24回登場し、1個だけ23回しか登場しないものがある。
すると選ばれなかった1個の1文字目が特定する。
次はその23個に該当する文字列の2文字目を見ると、3つは6回登場し、1個だけ5回しか登場しないものがある。
すると選ばれなかった1個の2文字目が特定する。
…とどんどん絞れば、119+23+5+1=148回の文字取得で済む。

int F;

vector<int> V[6][6];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	string s;
	FOR(x,6) FOR(y,6) V[x][y].clear();
	vector<int> C;
	FOR(i,119) C.push_back(i);
	string R;
	
	int mask=(1<<5)-1;
	FOR(i,4) {
		FORR(c,C) {
			cout<<(c*5+i+1)<<endl;
			cin>>s;
			V[i][s[0]-'A'].push_back(c);
		}
		x=-1;
		FOR(j,5) if((mask&(1<<j)) && (x==-1 || V[i][j].size()<V[i][x].size())) x=j;
		R.push_back('A'+x);
		C=V[i][x];
		mask ^= 1<<x;
	}
	
	FOR(i,5) {
		if(count(ALL(R),'A'+i)==0) R.push_back('A'+i);
	}
	cout<<R<<endl;
	cin>>s;
	assert(s=="Y");
}

まとめ

なんかGCJのInteractiveは意地でも二分探索にさせないという意気込みを感じる?