問題
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16944&pm=14636
複数のワインの中から、毒に反応する試験紙を使って「毒入りのワイン」を見つけ出し「毒入りではないワイン」をいかに多く集めることが出来るかという問題でした。（試験紙は毒に反応すると、次回以降に利用できなくなります）
方針
今回の方針です。
1. ワインを一通り検査する
まずは、各ワインを1回ずつ検査していきます。1回のラウンドで検査する範囲についてですが、以下の計算式で出していました。
n * (残っている試験紙の数 / 残っている毒の数) * (未チェックのワインの数 / 残りラウンド数) # nは任意の係数
そして、計算した範囲を試験紙の枚数で分割して、それぞれ検査を行います。
検査中に「試験紙が反応した数 == 毒の数」になった場合は、そこで検査を止めて、未検査のワインを全て保持するようにします。
また、毒に反応した範囲は 毒入りワインリスト に追加します。（毒入りワインリスト は範囲の大きいサイズから取り出す優先度付きキューです）
struct PoisonBarrel { vector<int> wineList; bool operator>(const PoisonBarrel &pb) const { return wineList.size() < pb.wineList.size(); } };
2. 追加のチェック
手順1で出した検査範囲だと「試験紙の数 < 毒の数」の場合はそもそも全部検査しきれずに終わることが多いです。逆に「試験紙の数 > 毒の数」の場合は全てのワインの検査後にラウンドが余るケースが発生するので、その場合は追加の検査を行っていきます。
追加の検査は試験紙が反応した範囲のワインに対して行います。
2.1 試験紙が反応した数 == 毒の数の場合
このケースでは「試験紙で検査した範囲に必ず毒が1個ある」という状態が確定しているので 毒入りワインリスト から試験紙が反応した範囲を取り出して、それを分割して検査します。m枚の試験紙を使って検査する場合はその範囲を m + 1 で分割します。m + 1 で分割している理由は、m枚の検査の結果から残りのワインの状態を確定させることが出来るからです。（いずれかの試験紙に反応すれば残りはOK、試験紙が反応無しだとOUT)
そして、毒が入っている範囲のワインを再度 毒入りワインリスト に追加します。
これをラウンドか試験紙がなくなるまで続けます。
2.2 試験紙が反応した数 != 毒の数の場合
このケースでは「試験紙で検査した範囲に複数の毒がある」という可能性があります。なので、この場合は m + 1 で分割しても、試験紙の結果から残りの状態を確定出来ません。
(もしかしたら毒かもしれないので確定できない)
このため、確定できなかったワインリストについては とりあえず保存領域 に置いておきます。
とりあえず保存領域 は、後の試験結果で毒が存在する箇所が全て確定した時にキープするワインのリストを置く場所です。
例えば「試験紙が反応した数 = 9, 毒の数 = 10」だとして、毒入りワインリスト から取り出した範囲から2個以上の試験紙の反応が出た場合。全ての毒の存在箇所が確定するので とりあえず保存領域 にあるワインを保存します。
このケースの場合はなるべく早い段階で複数の毒を検出したいので、試験紙の割り振り方を「m > 1」になるように調整しています。（例: [1, 1, 1, 1, 1] とあったら [3, 2, 0, 0, 0] となるように調整）
Examples
Example scores: 0) 0.01323285993742249 1) 0.20518911960377745 2) 0.009050017313019389 3) 1.0 4) 0.05072227596728843 5) 0.00401218710446807 6) 0.04226661200602016 7) 0.07289292284542803 8) 0.001466688380179619 9) 0.6574141709276845
