れどこだ目指すよ！　(；`・ω・）

ABC#011 D.大ジャンプ

その他, 参加ログ | 01:44

問題

XY座標の原点からゴール(X,Y)までジャンプで移動する。

ジャンプは、X,Y軸に平行に上下左右のどれかにDだけランダムに移動する。その確率は1/4。

ちょうどN回ジャンプしたときにゴール地点にいる確率を求めよ。

1<=N<=1000

1<=D<=10^9

-10^9 <= X,Y <= 10^9

考え方

まず、X,Yはそれぞれ絶対値をとっても問題ない。

XとYがそれぞれDで割り切れないといけない。

XとYをそれぞれDで割ったものがゴールへの最短回数になるが、今回はN回ちょうどでなければならない。

Nを、上下方向にn回、左右方向にm(=N-n)回使ったと仮定する。

y=Y/Dとすると、n回でyにならないといけないので、上にup回、下にdown回とすると、up-down=yかつup+down=nでないといけない。

なので、このとき、up=(y+n)/2回、down=n-up回動くことになる。

左右についても、right=(x+m)/2回、left=m-right回動くことになる。

(upやrightの計算の時、2で割って割り切れないといけないことに注意)

このときの確率は、(1/4)^N * Comb(N, up+down) * Comb(up+down, up) * Comb(right+left, right)になる。

nをN回分回して計算すればよい。

また、(1/4)^1000とかはdoubleの精度を超えるので、logとって計算するなどが必要。