新型コロナウイルスの唾液検査は複数人の検体を混ぜて行うことができ、混ぜた検体の中のいずれか一つにウイルスが入っていた場合に陽性となる。これを利用して検査回数の期待値をできるだけ減らしたい。
入力として初めに患者数$n$と陽性率$p$が与えられる。患者$0$, ..., 患者$n-1$は独立に確率$p$で陽性、確率$1-p$で陰性である。プログラムは$[0, n-1]$の患者番号の部分集合を指定してジャッジに検査を要求することができる。要求された患者番号の中で陽性者が一人でもいた場合、またその場合に限り、その検査は陽性となる。検査結果はそれぞれの検査ごとにジャッジから入力される。最後に、プログラムは全ての患者に対して陽性か陰性かの判定を出力しなければならない。出力が間違っていた場合、WAとなり、出力が正しかった場合(検査回数/$n$)の$-1$倍がそのテストケースの点数となる。
テストケースは$m$個存在し、それらの点数の平均が最終的な点数となる。
まず入力の一行目に$n$,
n p
r_1
r_2
...
プログラムは検査要求を行うときは次の一行を出力しなければならない。
INS l k_1 k_2 ... k_l
ただし、$l$は検査要求に含まれる人数であり、$k_i$は患者番号(
最後にプログラムは検査結果を次の一行で出力しなければならない。
ANS s_1 s_2 ... s_n
ただし、$s_i$は患者$i$の結果を表す数字であり、陽性なら1, 陰性なら0を出力しなければならない。
入力:
2 0.4
1
0
出力:
INS 2 0 1
INS 1 0
ANS 0 1
ただし、入力の2行目は出力の1行目が出力されたあと、入力の3行目は出力の2行目が出力された後に与えられることに注意せよ。
$n = 1000$ $p \sim \mathrm{Uniform}([0, 0.05])$ $m = 1000$
Rustをインストールする必要がある。
$ cargo build --release
$ cd target/release
$ ./judge <program> [<n>=1000] [<m>=1000] [<p_min>=0] [<p_max>=0.05] [<seed>=random]
テストケースと入出力のログがtest_cases/以下に生成され、結果は標準出力に吐かれます。毎回ランダムにテストケースを生成するので、比較する場合はシードを固定するなどしてください。
結果は、一人当たりの検査回数の平均値(-1倍していないもの)が出力されるので、値が小さい方が良いです。一応情報理論的な下限値も出力しています。
- naive: 愚直に一人ずつ検査するもの
- onestep:
$a$ 人ずつまとめて検査するが、陽性であれば一人ずつ検査し直すもの - poisson: ポアソン過程と近似して情報量をできるだけ大きくするように貪欲に検査していくもの
- optimal: 動的計画法を用いてn→∞で最適な検査を行うもの
一人当たりの検査回数の期待値は、$-(p\log_2 p + (1-p)\log_2 (1-p))$を切ることができない。optimalは、$p<0.3$程度であればほぼ情報理論的下限と同程度の性能が出ることがわかる。(optimal_analysis_linear.pngとoptimal_analysis_log.pngのグラフを参照)