かんプリンの学習記録

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

yukicoder No.2013 Can we meet?

yukicoder 形式的冪級数 式変形 期待値 競技プログラミング 解説

ほとんど公式解説と同じなので簡単に書きます。

問題はこちら

問題概要

2点{(x_1,y_1),(x_2,y_2)}がそれぞれ上下左右に{1}移動することを{N}回繰り返す．移動は左右には{\frac{A}{2(A+B)}}の確率で，上下には{\frac{B}{2(A+B)}}の確率で移動するとき、2点が{i}回目の移動直後に初めて重なる確率を{p_i}としたときの{\sum_{i=1}^{N}p_i×a_i}を求めよ．

  • {1\leq N\leq 10^5}
  • {0\leq x_1,y_1,x_2,y_2\leq 10^9}
  • {(x_1,y_1)\neq (x_2,y_2)}
  • {1\leq A,B\leq 10^6}
  • {1\leq a_i\leq 10^9}

解説

公式解説と同様に{x=|x_1-x_2|,y=|y_1-y_2|}とします．以降，{2N}回の移動で{(0,0)}から{(x,y)}への移動を考ます．
ここで，

  • {f(n):=(0,0)}から{2n}回の移動後に初めて{(x,y)}にいる確率
  • {g(n):=(0,0)}から{2n}回の移動後に{(x,y)}にいる確率
  • {h(n):=(0,0)}から{2n}回の移動後に{(0,0)}にいる確率

とすると，{g(n)=\sum_{i=0}^{n}f(i)×h(n-i)}が成り立ちます．公式解説と同様の方法で{g,h}を計算した後，{f,g,h}を形式的冪級数と考えると{f=g/h}として{f}を求めることができます．

計算量は{O(N\log{N})}です．

提出プログラム

https://yukicoder.me/submissions/779185

感想

結構きれいな形になった．