ABC333-Fが難しかったのでメモ

ABC333-F Bomb Game 2 https://atcoder.jp/contests/abc333/tasks/abc333_f

全ての人が消える確率が同じなので、自分の手番になったときに、そこから自分が最後の一人になる確率は、自分以外にあと何人残っているかだけで決まる。そこで、自分以外の残り人数を$${n}$$として、そこから自分が勝つ確率を $${V_n}$$ とする。

$${V_0}$$ は、「自分の手番になったときに、自分以外の残り人数が$${0}$$人のときの、自分が最後の一人になる確率」、つまり、自分が生き残っていて他に誰もいないので、確率は$${1}$$。

$${V_1}$$ は、自分以外に$${1}$$人いるので、次の場合分け：

• ①自分が残って、相手も残る $${1/4}$$

• ②自分が残って、相手が消える $${1/4}$$

• ③自分が消える $${1/2}$$

①の、自分も相手も残る場合は、何も起こらないことと同じなので、この確率は全体から取り除く。つまり、何か起こることだけを全体と見て遷移確率を作ればよい。

②は$${V_0}$$に遷移する。

③は自分が消えてしまうのでもう見なくてよい。

これらを合わせると、

$$
V_1 =\frac{1}{1-\frac{1}{4}} \frac{1}{4}V_0 =\frac{4}{3}  \frac{1}{4}V_0=\frac{1}{3}V_0
$$

$${V_2}$$も同様に（今度は相手は二人いるので）

• ①自分も残って、相手も二人とも残る $${\frac{1}{8}}$$

• ②自分が残って、相手が一人減る $${\frac{1}{2} \times \frac{1}{4} \times {}_2C_1 = \frac{1}{4} }$$

• ③自分が残って、相手が二人減る $${\frac{1}{2} \times \frac{1}{4} = \frac{1}{8} }$$

• ④自分が消える $${\frac{1}{2}}$$

よって

$$
V_2
=\frac{1}{1-\frac{1}{8}} \left( \frac{1}{4}V_1 + \frac{1}{8} V_0 \right)
=\frac{8}{7} \left( \frac{1}{4}V_1 + \frac{1}{8} V_0 \right)
=\frac{2}{7}V_1 + \frac{1}{7}V_0
$$

これを繋げていくと、$${V_n}$$ は

$$
V_n
= \frac{1}{1-\frac{1}{2^{n+1}}} \frac{1}{2} \sum_{i=0}^{n-1} \frac{1}{2^n} {}_nC_{i} V_i
= \frac{1}{2^{n+1}-1} \sum_{i=0}^{n-1} {}_nC_{i} V_i
$$

となって、$${V_0}$$から始めて$${V_{N-1}}$$までは$${\mathcal{O}(N^2)}$$ で計算できる。

さて、この $${V_n}$$ はあくまでも自分が先頭に来たときの、残り他人の人数別の自分が勝つ確率であった。$${1}$$番目の人にとっては、最初から自分が先頭なので $${V_{N-1}}$$ がそのまま自分が勝つ確率になるが、$${1}$$番目でない人においては、自分の前に何人脱落したかで生き残り人数が変わってくる。
そこで、自分が $${k}$$ 番目として、自分の前の$${k-1}$$ 人のうち$${l}$$ 人が生き残ったとすると、その状況になる確率は $${\frac{1}{2^{k-1}} {}_{k-1}C_l }$$、また、その状況では自分以外に $${N-k+l}$$ 人生き残っているので、そこから自分が勝つ確率は $${V_{N-k+l}}$$。

よってそれらを掛けてたしてあげれば、$${k}$$番目の人が勝つ確率になる。$${P_k}$$を$${k}$$番目の人が勝つ確率とすると、

$$
P_k = \frac{1}{2^{k-1}}\sum_{l=0}^{k-1}  {}_{k-1}C_l V_{N-k+l}
$$

これは $${V_n}$$ をあらかじめ計算しておけば $${\mathcal{O}(N^2)}$$ で計算できる。