2019年4月25日木曜日

ABC 011 D - 大ジャンプ

ABC 011 D - 大ジャンプ

以下、X,YX, Yは最初からDDで割ったものを扱い、D=1D=1とする。xx軸に沿ってk+k^+回+1+1進み、k−k^-回−1-1進み、yy軸に沿ってl+l^+回+1+1進み、l−l^-回−1-1進む場合を考える。このように進む確率をP(k+,k−,l+,l−)P(k^+, k^-, l^+, l^-)とすると、
P(k+,k−,l+,l−)=(Nk+)(N−k+k−)(N−k+−k−l+)4−NP(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+,l−k^+, 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(N−k+−k−+Y)l−=12(N−k+−k−−Y) \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 \}について（k−k^-, l+l^+, l−l^-が有効な値なら）P(k+,k−,l+,l−)P(k^+, k^-, l^+, l^-)を足し合わせると、それが答えになる。

しかし、上のPPをそのまま計算すると倍精度ではオーバーフローしてしまうので、log⁡\logを経由することにする:
P(k+,k−,l+,l−)=exp⁡(log⁡(Nk+)+log⁡(N−k+k−)+log⁡(N−k+−k−l+)−Nlog⁡4)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)=log⁡n!−log⁡m!−log⁡(n−m)!\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. log⁡n!=∑i=1nlog⁡i\log n! = \sum_{i=1}^n \log i ↩︎

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

投稿者