この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は意地でも二分探索にさせないという意気込みを感じる?