No.2389 Cheating Code Golf
タグ : / 解いたユーザー数 54
作問者 : 👑
cleantted
PCTprobability
👑 
Mizar
👑 
amentorimaru
問題文
VR Code Golf Contestでは、 $N$ 問の問題に対してプログラムのソースコードをそれぞれ提出し、問題を正解することができたソースコードの短さを競います。
このコンテストでは、全ての問題の合計で $M$ 回まで不正解の提出をしてよいです。不正解の提出の回数の合計が $M$ 回を超えると、以降は全ての問題に対して提出することができなくなります。
また、一度正解した問題に対して再提出をすることはできません。
$x$ 文字のソースコードで問題を正解した場合、その問題に不正解の提出をした回数にかかわらず、提出者は得点 $\frac{1}{x}$ を得ることができます。
羊くんは、このコンテストで乱択を用いた不正を行うことにしました。
羊くんは、 $i$ 問目 $(1≤i≤N)$ の問題に対して、乱択を用いずに確率 $1$ で正解できる $A_i$ 文字のソースコードと、乱択を用いて確率 $\frac{1}{P_i}$ で正解できる $B_i$ 文字のソースコードを持っています。
ここで、乱択を用いたコードが正解となるか不正解となるかは各提出ごとに独立に決められます。また、$1$ 回提出するごとに正解か不正解かを確認することが出来ます。
以下の条件を満たすように提出するソースコードを決めていったとき、得られる得点の合計の期待値を求めてください。
- 乱択を用いた提出が全て不正解になったとしても、全問正解できる。
- 上記を満たす方法のうち、得られる得点の合計の期待値が最大になる。
入力
$N\ M$ $A_1\ B_1\ P_1$ $A_2\ B_2\ P_2$ $\vdots$ $A_N\ B_N\ P_N$
- 入力は全て整数
- $1\leq N\leq 12$
- $0\leq M\leq 40$
- $1\leq A_i\leq 10^6$
- $1\leq B_i\leq 10^6$
- $1\leq P_i\leq 10^6$
出力
得られる得点の合計の期待値を出力せよ。
サンプル
サンプル1
入力
3 1 8 2 3 8 6 2 8 8 2
出力
0.506944444444444
$3$ 問目では乱択を用いず、その他の問題は $1$ 回乱択が失敗するまで乱択を用いながら、 $1$ 問目、 $2$ 問目の順に解いていくのが最適となります。
このとき、 $1$ 問目と $2$ 問目の両方で乱択が成功する場合と、 $1$ 問目で乱択が成功し $2$ 問目では乱択が失敗する場合と、 $1$ 問目で乱択が失敗し $2$ 問目では乱択を用いない場合が考えられます。
$1$ 問目と $2$ 問目の両方で乱択が成功する確率は $\frac{1}{P_1P_2}=\frac{1}{6}$ で、このとき得点 $\frac{1}{B_1}+\frac{1}{B_2}+\frac{1}{A_3}=\frac{19}{24}$ を得ます。
$1$ 問目で乱択が成功し $2$ 問目では乱択が失敗する確率は $\frac{1}{P_1}\left(1-\frac{1}{P_2}\right)=\frac{1}{6}$ で、このとき得点 $\frac{1}{B_1}+\frac{1}{A_2}+\frac{1}{A_3}=\frac{3}{4}$ を得ます。
$1$ 問目で乱択が失敗し $2$ 問目では乱択を用いない確率は $1-\frac{1}{P_1}=\frac{2}{3}$ で、このとき得点 $\frac{1}{A_1}+\frac{1}{A_2}+\frac{1}{A_3}=\frac{3}{8}$ を得ます。
よって、得られる得点の合計の期待値は $\frac{1}{6}\cdot\frac{19}{24}+\frac{1}{6}\cdot\frac{3}{4}+\frac{2}{3}\cdot\frac{3}{8}=0.506944444444444\ldots$ となります。
サンプル2
入力
3 0 8 2 3 8 6 2 8 8 2
出力
0.375
サンプル3
入力
10 40 100 200 6 200 100 10 100 50 30 300 400 2 150 200 3 1000 200 6 200 1000 6 100000 100 6 100 100000 6 100 200 100000
出力
0.0845021746904274
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。