2019年4月25日木曜日

ABC 011 D - 大ジャンプ

ABC 011 D - 大ジャンプ

以下、X,YX, Yは最初からDDで割ったものを扱い、D=1D=1とする。xx軸に沿ってk+k^++1+1進み、kk^-1-1進み、yy軸に沿ってl+l^++1+1進み、ll^-1-1進む場合を考える。このように進む確率をP(k+,k,l+,l)P(k^+, k^-, l^+, l^-)とすると、
P(k+,k,l+,l)=(Nk+)(Nk+k)(Nk+kl+)4NP(k^+, k^-, l^+, l^-) = \binom{N}{k^+}\binom{N-k^+}{k^-}\binom{N-k^+-k^-}{l^+}4^{-N}

である。あとは(X,Y)(X, Y)にたどりつくようなk+,k,l+,lk^+, k^-, l^+, l^-の組み合わせについてPPを足し合わせればよい。具体的には、k+k^+が与えられたとき、k+k=Xk^+ - k^- = X, l+l=Yl^+ - l^- = Y, k++k+l++l=Nk^+ + k^- + l^+ + l^- = Nより、残りは以下のように定まる。
k=k+Xl+=12(Nk+k+Y)l=12(Nk+kY) \begin{aligned} k^- & = & k^+ - X \\ l^+ & = & \frac{1}{2}(N-k^+-k^-+Y) \\ l^- & = & \frac{1}{2}(N-k^+-k^--Y) \end{aligned}

したがって、各k+{0,1,...,N}k^+ \in \{0, 1, ..., N \}について(kk^-, l+l^+, ll^-が有効な値なら)P(k+,k,l+,l)P(k^+, k^-, l^+, l^-)を足し合わせると、それが答えになる。

しかし、上のPPをそのまま計算すると倍精度ではオーバーフローしてしまうので、log\logを経由することにする:
P(k+,k,l+,l)=exp(log(Nk+)+log(Nk+k)+log(Nk+kl+)Nlog4)P(k^+, k^-, l^+, l^-) = \exp \Bigl (\log\binom{N}{k^+} + \\\log\binom{N-k^+}{k^-} +\log \binom{N-k^+-k^-}{l^+} -N \log 4 \Bigr)

log(nm)=logn!logm!log(nm)!\log\binom{n}{m}= \log n! - \log m! - \log (n-m)!だから、階乗の対数が求まればよい。今回はNNが小さいので素朴に足す1だけでも問題ないし、大きい場合も精度のよい漸近公式がいろいろある。2

想定解法ではなさそうと思いながら書いた。対数を取る方法は、ABC 094 - Dがわからなくて苦し紛れに書いたのをコピペしただけなのだが、(精度的な意味で)どのくらい頑健なのかよくわかっていない。

想定解法は、最初から確率で遷移することで、値が大きくならないようにするというものだった。パスカルの三角形の(nm)/2n\binom{n}{m}/2^nバージョンは頭に入れておいたほうが良さそう。


  1. logn!=i=1nlogi\log n! = \sum_{i=1}^n \log i ↩︎

  2. 言語によってはそもそも標準ライブラリにlgammaがあったりするらしい。 ↩︎