後ろから考えると楽になる問題。
後ろからだと、例えば以下のような問題に言い換えられる。
道中で傷を同時に負っている最大個数が、元の問題での $K$ に相当する。
無駄に傷を治さないでいる必要は無いので、ポーションを見つけ次第すぐに治すのが最適。
そうした場合の $K$ が $K_{min}$ となる。
以下のアルゴリズムで貪欲的に処理できる。
タイトルからして、多分原案は、1/2で爆発する爆弾を渡していく感じだった?
$DP[n,i]$ を、「$n$ 人いて、先頭から $i$ 番目の人が最後まで生き残る確率」とする。
$n=1$ のとき、明らかに $DP[1,1]=1$ で、そこから $n$ を増やしていきたい。各 $i$ に対する $DP[N,i]$ が答え。
n\i 1 2 3 ... 1 1 2 ? ? 3 ? ? ? 4 ? ? ? ?
$DP[n-1,j]$ から $DP[n,i]$ を求める時に嫌なのが、
ので、ただでさえ $N^2$ ある状態で、遷移にも $N$ かかり、全体で $O(N^3)$ となるところ。
n\i 1 2 3 n\i 1 2 3 3 ○ ○ ○ 3 ○ ○ ○ DP[3,j] から DP[4,i] に ↓↙↙ ↘↓↙ それぞれ異なる係数がかかる 4 ○ 4 ○ ※ゲームの流れ的には上記の矢印の向きは逆だが、 今は最終状態から遡ってDPを埋めているため、埋める順序で表している
だが、まぁ、上手くまとめられることを期待して、とりあえずそれぞれの係数を考えてみる。
$K_{n,i}$ を、「$n$ 人いて、次に列から除外されるのが先頭から $i$ 番目の人である確率」とする。
すると、1巡目で除外される確率は「$i-1$ まで除外されず、$i$ で除外」の場合なので、$\dfrac{1}{2^i}$ である。
誰も除外されず1巡するのは $\dfrac{1}{2^n}$ で、元に戻る自己ループ形式の確率となって、
となる。要は、分子だけを見ると $2^{n-1},...,8,4,2,1$ などと末尾から2の累乗となっている。(全て合計すると $2^n-1$)
$T_{n,i,j}$ を、「$n$ 人いて、先頭から $i$ 番目の人が生き残って、次、$n-1$ 人の状態が $j$ 番目から始まる確率」とする。
これが、$DP[n-1,j]$ から $DP[n,i]$ への係数となる。
$T_{n,i,j}$ は、$i$ より $j$ 人前の人が除外される確率なので、
n=5 除外される人 その確率(Tnij)の分子(分母は 2^n-1 = 31) i\j 1 2 3 4 i\j 1 2 3 4 1 5 4 3 2 1 1 2 4 8 2 1 5 4 3 2 16 1 2 4 3 2 1 5 4 3 8 16 1 2 4 3 2 1 5 4 4 8 16 1 5 4 3 2 1 5 2 4 8 16
こんな感じになる。
つまり、DPの遷移は以下のような感じになる。
DP[n,i] n\i 1 2 3 4 n\i 1 2 3 4 n\i 1 2 3 4 4 ○ ○ ○ ○ 4 ○ ○ ○ ○ 4 ○ ○ ○ ○ x1 x2 x4 x8 x16 x1 x2 x4 x8 16 x1 x2 ... ↓↙↙ ↙ ↘↓↙↙ ↘↘↓↙ 5 ○ 5 ○ 5 ○ (※それぞれさらに 1/31 倍するが、表記上は省略)
よく見ると、$DP[5,1]$ を愚直に計算すると、$DP[5,2]$ はその結果から計算できることがわかる。
よって、$DP[n,1]$ さえ $O(n)$ で求めれば、$DP[n,2]$ 以降は $O(1)$ で計算でき、全体で $O(N^2)$ で求めることができる。