かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC333 F - Bomb Game 2

問題はこちら

目次
  1. 問題概要
  2. 解説
  3. 提出プログラム
  4. 感想

問題概要

{N}人の人が一列に並んでいる．先頭の人を{\frac{1}{2}}の確率で列から取り除き，{\frac{1}{2}}の確率で列の末尾に移す．人{i}が最後の1人になる確率を求めよ．

  • {2\leq N\leq 3000}

解説

{i}人の列で先頭から{j}番目の人が最後に残る確率を{P_{i,j}}とします．
先頭の人がどうなるかで場合分けを行います．

  • 先頭の人が取り除かれるとき：{1}番目だった人は取り除かれ，{j}番目だった人は{j-1}番目になる．
  • 先頭の人が末尾に移されるとき：{1}番目だった人は{i}番目になり，{j}番目だった人は{j-1}番目になる．

したがって{P_{i,j}}は以下のようになります．

  • {P_{1,1}=1}
  • {P_{i,1}=\frac{1}{2}P_{i,i} (i\geq 2)}
  • {P_{i,j}=\frac{1}{2}P_{i-1,j-1}+\frac{1}{2}P_{i,j-1} (i\geq j\geq 2)}

{P_{i,1}=\frac{1}{2}P_{i,i}}のせいで遷移に循環があります．
{x=P_{i,i}}と置くと{P_{i,j}}は{x}の一次式{ax+b}で表すことができるので，{j}の昇順に{a,b}を持ってDPを行うと{P_{i,i}=x=ax+b}となるため，{x=\frac{b}{1-a}}となります．今回の制約では{(1-a)\bmod 998244353}が{0}になることは無いため正しく求めることができます．時間計算量は{O(N^2)}で，空間計算量は{O(N)}です．

提出プログラム

https://atcoder.jp/contests/abc333/submissions/48609390 (見やすさのため空間計算量O(N^2)で書いてます)

感想