考察
M人の体調結果はM bitの文字列なので区別できる候補は高々2^M個である。よってN本を必ず識別するにはM≥ceil(log2 N)が必要で、各bottle番号をそのM bit符号として配れば同じ人数で達成できる。
採用する候補: 0-based bottle番号のbinary bitごとに友人へ飲ませる
棄却する候補: 各友人に一つの連続区間だけを割り当てる二分探索的質問
結果は一晩後に一括で返りadaptiveに次の質問を選べないため、固定区間だけでは一般に最小人数で全番号を符号化できない。
最小のM with 2^M≥Nを出力する。各bit iについて、(j-1)のi bit目が1であるbottle jを昇順に列挙して人数と一覧を出しflushする。長さMのSを読み、S_iをbit iとして整数xを復号しx+1を出力する。
典型の発動条件
情報量下界
発動条件: 一回の非adaptive検査で各参加者から0/1だけが返る。
結果pattern数2^Mが候補数N以上必要というpigeonhole principleで最小人数を下から抑える。
binary incidence coding
発動条件: 各対象を、どの検査群へ含めるかのsubsetで識別したい。
対象indexのbit列をmembership vectorとして使い、観測vectorからindexを復元する。
問題固有の要素
友人が腹痛になる条件は腐った一本を飲んだかだけなので、複数bottleを混ぜる行為がOR混同を起こさず、唯一の腐敗bottleのmembership codeを直接観測できる。
別の問題へ持ち帰る視点: 欠陥がちょうど一つのgroup testingは、対象ごとのbinary code設計に一致する。
正当性
M=ceil(log2 N)なら0,…,N-1は全てM bitで一意である。友人iへi bit目が1のbottleだけ飲ませると、腐ったbottle xによる体調列Sはxのbinary表現と完全に一致する。 各bottleに相異なるM-bit codeを割り当て、体調文字列をそのまま腐敗番号へ復号でき、情報量下界と一致する。
実装上の注意
- editorialの0-based bottle jを出力ではj+1へ戻す。Sの先頭をbit 0として配布規則と復号のbit順を一致させ、各出力後にflushする。
復習の核
- Nが2の冪の場合と直後、全0のcodeに対応するbottle 1、bit順を逆に読んだ場合をlocal interactorで確認する。
計算量と制約
時間
O(N log N)、各bitの飲む集合を列挙。
空間
O(N)、一集合ずつ出力、復号文字列O(log N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N is an integer.; 2 \leq N \leq 100
出典