ABC011 D 大ジャンプ - 足跡-sokuseki-

問題概要

スタート地点の座標は $(0, 0)$ で、ゴール地点の座標は $(X, Y)$ とする。
1回のジャンプで、それぞれ $\frac{1}{4}$ の確率で以下の4つのうちどれかを行う。

$x$ 軸方向に $+D$ だけ移動する
$x$ 軸方向に $-D$ だけ移動する
$y$ 軸方向に $+D$ だけ移動する
$y$ 軸方向に $-D$ だけ移動する

ちょうど $N$ 回のジャンプでスタート地点からゴール地点に到達できる確率を求めよ。

制約
$0 \le N \le 1000$
$1 \le D \le 10^9$
$- 10^9 \le X, Y \le 10^9$

解法

$x$ 軸方向に $i$ 回移動するとき、 $y$ 軸方向に $n-i$ 回移動することになる。
また、このとき、 $x$ 軸の正の方向に $j$ 回移動すると、 $x$ 軸の負の方向に $i-j$ 回移動することになるので、到達点の $x$ 軸座標は $D j - D ( i - j )$ になる。
$y$ 軸方向にも同様に考えて、 $y$ 軸の正の方向に $k$ 回移動すると、 $y$ 軸の負の方向に $n-i-k$ 回移動することになるので、到達点の $y$ 軸座標は $D k - D ( n - i - k )$ になる。
到達点の座標が $(X, Y)$ であればよい。

つまり、 $x$ 軸方向の移動回数 $i$ 、 $x$ 軸の正の方向の移動回数 $j$ 、 $y$ 軸の正の方向の移動回数 $k$ を全探索して、その到達点の座標が $(X, Y)$ ならば、その確率を答えに足しあわせればよい。

$i$ 回の移動のうち正の方向に $j$ 回移動するのは $_i C _j$ 通りあり、 $i$ 回正負のどちらかに移動するのは $2^i$ 通りあるので、 $i$ 回の移動のうち正の方向に $j$ 回移動する確率は $\frac{ _i C _j }{2^i}$ である。
よって、 $i$ 回の移動のうち正の方向に $j$ 回移動する確率を前計算することで、 $O(N^2)$ で求めることができる。