問題一覧 > 通常問題

No.2389 Cheating Code Golf

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 小数誤差許容問題　絶対誤差または相対誤差が$10^{-6}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : / 解いたユーザー数 54
作問者 : 👑 獅子座じゃない人獅子座じゃない人 / テスター : cleanttedcleantted 👑 PCTprobabilityPCTprobability 👑 MizarMizar 👑 amentorimaruamentorimaru
2 ProblemId : 9742 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-07-20 17:55:21

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。