AtCoder Beginner Contest 011 D - 大ジャンプ
AtCoder Beginner Contest 011 D - 大ジャンプ に関する記事です．
問題へのリンク
状況
2020/08/07 のあさかつで出題されました． 解けたつもりでしたが，時間内にはコードが書ききれませんでした． その後も考えたところ，結局，解けてはいなかったことがわかりました． 誤差が累積したのか，と思ったのですが，そうではなくて，double で表現できる範囲を超えていたのが問題でした．
解法
適当に回転することを考えれば，$X \geq 0$, $Y \geq 0$ としてよい． $X$ や $Y$ が $D$ の倍数でなければ，到達できない． $D$の倍数になっているときは，これらを $D$ で割っておくことで，$D = 1$ と考えることができる． $x_P$, $x_N$, $y_P$, $y_N$ を各々x/y方向への正/負の移動回数とすると， $x_P - x_N =X$, $y_P - y_N = Y$ となる．$p = x_P + y_P$, $n = x_N + y_N$ と書くと， $p + n = N$, $p - n = X + Y$ より $p = (N + X + Y) / 2$, $n = (N - (X + Y)) / 2$ なので，以下が必要．
- $X + Y \leq N$
- $N + X + Y$ は偶数
逆に，この2つが成り立っていれば，$x_N = 0, 1, \ldots, n$ に対して，$x_P$, $y_N$, $y_P$ が定まる． これらの各々の組に対して，そのようになる確率は $$\frac1{4^N} \binom{N}{x_N}\binom{x_P + y_P + y_N}{x_P}\binom{y_N + y_P}{y_N}\binom{y_P}{y_P}$$ であるから，これらの和を求めれば良い．
計算上の問題点と解決
上の解法までは到達したのですが，その後の計算ができませんでした． 2項係数$\binom{n}{r}$ は，$(n(n-1)\cdots(n-r+1)) / (r(r-1)\cdots1)$ を計算すれば良いので，全体として $O(N^2)$ で計算でき，$N \leq 1000$ ですから，計算量的には問題ありません． 問題は値が大きくなることで，DBL_MAX の値は $1.8\times10^{308}$くらいなので， $4^{1000} = 2^{2000} \approx 10^{600}$ は，表現できません． またたとえば，$\binom{1000}{500}$ は，大雑把に $2^{1000} \approx 10^{300}$ くらいあり，このまま正直に計算すると溢れます．
そこで，$x_N + x_P + y_N + y_P = N$ であることに注目し，$f(n, r) = \binom{n}{r}/4^r$ と書くと， 上の式は，$f(N, x_N) \cdot f(x_P + y_P + n_Y, x_P) \cdot f(y_N + y_P, y_N) \cdot f(y_P, y_P)$ となります． $f(n, r)$ は，次のようにすることで，溢れさせずに計算できます:
$$ f(n, r) = (n / (4r)) \cdot ( (n-1) / (4(r-1))) \cdot \cdots \cdot ( (n-r+1) / (4\cdot 1))$$
まあ，LDBL_MAX は $1.2\times 10^{4932}$ なので，long double を使えばそれで終わり，という話もありますが．
