F - Bomb Game 2 解説
by 
maspy
同じ計算量での別解 / 計算量改善の方法
\(O(N^2)\) 時間で解く別解を説明したあと，\(O(N\log^2N)\) 時間に高速化する方法を説明します．
[1] \(O(N^2)\) 時間で解く別解
\(i\) 番目の人が勝つ確率を dp 等を使わず直接数式にしましょう． まず，本問のゲームを次のように言い換えます．
- 当たりまたは外れが確率 \(1/2\) で出るくじを引き，結果によらず列の末尾に移動する． 全員が 1 回以上当たりくじを引くまで繰り返す．
- 最後に当たりを引いた人が，人 \(i\) である確率を求めよ．
人 \(i\) がちょうど \(k\) 回目で当たりくじを引き，それが全員の中で最後である確率を \(p_k\) とします．\(p_k\) は次のような値を全員についてかけたものになります．
- 人 \(i\)：\(k-1\) 回まで外れ，\(k\) 回目が当たりである確率 \(2^{-k}\).
- 初期位置で人 \(i\) よりも左に居る人：最初の \(k\) 回以内に当たりくじを引く確率 \(1-2^{-k}\).
- 初期位置で人 \(i\) よりも右に居る人：最初の \(k-1\) 回以内に当たりくじを引く確率 \(1-2^{-k+1}\)．
したがって，
\[p_k = 2^{-k}\cdot (1-2^{-k})^{i-1}\cdot (1-2^{-k+1})^{N-i}\]
となります．したがって多項式 \(f_i\) を
\[f_i = \frac12x\cdot \biggl(1-\frac12 x\biggr)^{i-1}\cdot (1-x)^{N-i}\]
により定めれば，人 \(i\) に対する答は \(\sum_{k=1}^{\infty}f_i(2^{-k})\) となります．
\(j>0\) に対して \(c_j = \sum_{k=0}^{\infty}(2^{-kj})\) により \(c_j\) を定めれば，答は \(\sum_{j=1}^N([x^j]f_i(x))\cdot c_j\) と書けます．
\(f_i(x)\) から \(f_{i+1}(x)\) を求める計算が低次の多項式を掛けて割る操作で \(O(N)\) 時間で計算できるので，\(f_1, \ldots, f_N\) のすべてを合計 \(O(N^2)\) 時間で計算でき，本問を解くことができます．
- 解答例（コンテスト中実装）：https://atcoder.jp/contests/abc333/submissions/48572822
[2] \(O(N\log^2N)\) 時間での解法
最後の \(\sum_{j=1}^N([x^j]f_i(x))\cdot c_j\) は，適切に多項式 \(g\) を定義すれば \([x^N]f_i(x)g(x)\) と書けます．
結局，おおよそ次のようにかけることが分かります：
\(1\) 次式 \(L_1(x), \ldots, L_N(x), R_1(x), \ldots, R_N(x)\) が与えられる．\(N\) 次式 \(g(x)\) も与えられる．
各 \(i\) に対して \([x^N] L_1(x)\cdots L_{i-1}(x) g(x) R_{i+1}(x)\cdots R_N(x)\) を求めよ．
これは典型的な分割統治法により \(O(N\log^2N)\) 時間で解けます．次の解説記事の「パターン 2」を参考にしてください．
（注：やや慣れている人向けの解説になっていて，ABC rated レベルだとかなり難しいと思います．https://atcoder.jp/contests/abc281/tasks/abc281_h の解説等も参考になるかもしれません．）
今回は \(L_i(x)\) や \(R_i(x)\) がすべての \(i\) に対して同じであり，その \(n\) 個の積を \(O(n)\) 時間で計算できるため，いくらか実装が易しくなると思います（区間積の bottom up な計算が不要）．
投稿日時:
最終更新: