問題概要
本問はインタラクティブ問題である．
$1$ から $n$ で番号付けられた $n$ 本のジュースがあるが，その内ちょうど $1$ 本は腐っており，それを飲むと◯ぬ．腐ったジュースを特定するために，次のことを行う．
- 整数 $m $ を選び，$m $ 人の友人を呼ぶ．
- それぞれの友人に対して（独立に）ジュースの部分集合を選び，飲ませる．
- 各友人が体調を◯んだか否かの情報を受け取る．
- 情報は $\text{'0', '1'}$ からなる長さ $m $ の文字列 $S$ で与えられ，$S_i = \text{'1'}$ のとき，友人 $i$ が◯んだことを示す．
上記の手続きにより腐ったジュースを特定するとき，呼ぶ友人を最小化した上で，腐ったジュースの番号を報告せよ．
制約
- $2 \leq n \leq 100$
解法
実は，飲み物の種類は異なりますがこれは有名問題[要出典]で，数学だか論理パズルだかの文脈で「毒ワイン問題」というような名称で知られています．ということで，Google 検索を使いこなすことができれば，問題を解くことができます．……というのではあんまりにもあんまりなので，真面目にやっていきます*1．
$m $ 人の友人を被検体にしたとき，得られる $S$ は高々 $2^m $ 種類です．このことから，$2^m < n$ なる $m $ では $n$ 通りある状態を区別できません．$n \leq 2^m $ なる $m $ であれば解ける可能性があるわけですが，辺々対数をとると $\log_2 n \leq m $ であり，人間の人数は整数であることに着目すると，$m = \lceil \log_2 n \rceil$ というのが $m $ の候補です．この $m $ で腐ったジュースを特定できれば，（これ未満の $m $ は不適であることから）最適な人数であると分かります．
$\log_2$ が出てきたことからバイナリ的な雰囲気を感じるので，その方向で考えてみます．かなり天啓的ですが，友人 $i$ を $2$ 進表現した整数の右から $i$ 桁目 ($1$-indexed) に対応付けてみましょう．飲ませ方の戦略としては，
- 友人 $i$ には $i$ 桁目が $1$ であるようなジュースのみを全て飲ませる．
としてみます．これで友人 $i$ が◯んだとすれば，腐ったジュースの番号は $i$ 桁目が $1$ であることが分かります*2．同様のことが全ての友人について言えるので，腐ったジュースの番号において $1$ であるビットを $m $ 桁目までの範囲で特定できます．逆に，そういった $i$ が存在しなければ，$2^m = n$ 番のジュースが腐っています．これで $S$ から腐ったジュースの番号を復元できるので，問題を解くことができます．
コード
int main() { IN( int, N ); int M = 0; for ( ; ( 1 << M ) < N; ++M ); cout << M << endl; REP( i, M ) { VI drink; REP( j, 1, N + 1 ) { if ( j & ( 1 << i ) ) { drink.PB( j ); } } cout << SZ( drink ) << ' ' << drink << endl; } IN( string, S ); reverse( ALL( S ) ); int res = 0; FOR( c, S ) { res <<= 1; res += c - '0'; } cout << ( res ? res : N ) << endl; return 0; }
