ARC085 / ABC078 C HSI - 足跡-sokuseki-

問題概要

プログラミングコンテストの 'YES' か 'NO' で答える問題でTLEした。
テストケースは $N$ ケースあり、そのうち $M$ ケースでTLEしていた。
そこで、 $M$ ケースではそれぞれ実行に $1900$ ms かかって $\frac{1}{2}$ の確率で正解し，残りの $N - M$ ケースではそれぞれ実行に $100$ ms かかって必ず正解するプログラムへ書き換えた。
一度ですべてのケースに正解するまで提出を繰り返したときの、プログラムの実行時間の総和の期待値を求めよ。

制約
$1 \le N \le 100$
$1 \le M \le min(N, 5)$

解法

この問題の答えを $y$ msとすると、あるケースで不正解だった場合、それ以降の提出の実行時間の総和の期待値は $y$ msになる。
よって、1回の提出での実行時間の総和を $x$ ms、すべてのケースに正解する確率を $p$ とすると、
$y = x + (1 - p)y$
という式が成り立ち、この式を整理すると、この問題の答え $y$ は
$y = \frac{x}{p}$
になる。

ここで、
$x = 1900M + 100(N - M)$
$p = \frac{1}{2^M}$
であるので、代入すると
$y = ( 1900M + 100(N - M) )2^M$
となる。

Submission #2012637 - AtCoder Regular Contest 085