ABC 337 E — Bad Juice

考察

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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Bad Juice の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 情報量下界・query符号設計

主題
追加で学ぶ技能
    なし
    既習技能
    • 対話protocolを守って情報を取得する: judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。

    主タグ: 情報量下界・query符号設計

    補助タグ: 対話protocolとquery設計

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 情報量下界・query符号設計

    • 応答列の総数からquery数の下界を証明し、それに一致するcodeword割当と復号を構成できる。

    先に読む単元:

    • 対話protocolを守って情報を取得する — 問い合わせ形式・回数上限・応答依存性・交互手番・合法な応答・flushを明示し、アルゴリズムをjudgeとの対話列として安全に実行する。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題