AtCoder Beginner Contest 011 D - 大ジャンプ

お題箱より。

解法

まずは計算しやすいようにいくつか前処理をします。

ゴールまでの $X, Y$ 軸方向それぞれの距離を $D$ で割ることで「正の方向にジャンプ○回分」という値に変換します。ここで割り切れない場合、答えは $0$ です。今後は $D$ で割った後の値を単に $X, Y$ と表記します。

答えを求めるにあたり、 $N$ 回のジャンプのうちいくつを $X$ 軸に割り振るかを全探索します。ここで $a$ 回を $X$ 軸に割り振るとすると、ゴールに止まるために正負それぞれの方向に何回飛ばないといけないかが決まります。具体的には正の方向に $x_{1}$ 回、負の方向に $x_{2}$ 回とすると

$x_{1} + x_{2} = a$
$x_{1} - x_{2} = X$

という連立方程式の解として求めることができます。これを解いたときに $x_{1}, x_{2}$ の両方が非負整数になる必要があり、そうでない場合この $a$ ではゴール不可能です。

同様に $Y$ 軸についても、 $N-a$ 回を正負それぞれの方向に飛ぶ回数 $y_{1}, y_{2}$ に割り振ります。

すると $a$ を固定した時に「合計 $N$ 回のジャンプがどう並んでいるか」という場合の数は、

まず $N$ 回を $X$ 軸と $Y$ 軸に割り振る： $_{N}C_{a}$ 通り
$X$ 軸の $a$ 回を割り振る： $_{a}C_{x_{1}}$ 通り
$Y$ 軸の $N-a$ 回を割り振る： $_{N-a}C_{y_{1}}$ 通り

の掛け算で計算できて、それぞれの並べ方について「全てのジャンプがその並びの通りになる確率」は $(\frac{1}{4})^{N}$ なのでこれを掛けると答えを求めることができます。

もしこれが「有理数を $\bmod 10^{9}+7$ で計算した余りを求めよ」という形式であればあとは階乗や逆元のライブラリ任せで計算できます。ただ今回は小数で計算する必要があるのでちょっと面倒です。

小数での確率計算

なぜ面倒かというと、浮動小数点数型には桁数の上限/下限があるからです。例えばC++で

double P = 1.0;
for(int i=1; i<=N; i++) P *= i;

と小数での階乗計算をすると、 $N \ge 171$ で桁数が足りなくなり、出力すると inf と表示されるようになります。小さい方の値である $(\frac{1}{4})^{N}$ も、 $N \ge 538$ では 0 になります。（ともに私の手元環境で実験）

つまり急速に大きくなる値（場合の数）と急速に小さくなる値（ある1つの場合が実現される確率）を別々に計算して掛け算すると正しい値が求められません。上手く並行して計算することで桁数をコントロールする必要があります。

例えば $N$ 回のジャンプを $X$ 軸と $Y$ 軸に割り振るところを考えます。これを確率込みで考えて、

$N$ 回のジャンプが、それぞれ $X, Y$ 軸どちらのものであるかを順番に決めていく。 $X$ 軸になる確率、 $Y$ 軸になる確率はともに $\frac{1}{2}$ である。 $X$ 軸に割り振った回数がちょうど $a$ 回となる確率はいくつか？

という値を求めましょう。

これはDPで求めることができます。状態を次のように定義します。

$dp\lbrack i \rbrack\lbrack j \rbrack =$ ジャンプ $i$ 回について既に決めている時に、そのうち $j$ 回が $X$ 軸のものである確率

初期条件は $dp\lbrack 0 \rbrack\lbrack 0 \rbrack$ です。 $dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移は、次に決めたものが $X$ 軸であれば $dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack$ に、 $Y$ 軸であれば $dp\lbrack i+1 \rbrack\lbrack j \rbrack$ に、それぞれ確率 $\frac{1}{2}$ を係数として遷移します。

このDPの遷移は、「パスカルの三角形」の構造そのものです。

f:id:betrue12:20200529074208p:plain

このDPの結果である $dp\lbrack N \rbrack\lbrack a \rbrack$ が求めたい値であり、これは $_{N}C_{a} (\frac{1}{2})^{N}$ と一致します。

$X$ 軸の中、 $Y$ 軸の中それぞれの割り振りも、同じ構造になっているので同様に求められます。こちらも正になる確率、負になる確率がともに $\frac{1}{2}$ なので同じDPの結果を使うことができて、それぞれ $_{a}C_{x_{1}} (\frac{1}{2})^{a}$ と $_{N-a}C_{y_{1}} (\frac{1}{2})^{N-a}$ が求められます。

これらの積が、元々求めたかった

$\displaystyle {}_{N}C_{a}\times {}_{a}C_{x_{1}}\times {}_{N-a}C_{y_{1}}\times (\frac{1}{4})^{N}$

と一致します。 $a$ を全探索してこの値を全て合計することで、答えを求めることができます。

計算量について

もし十分大きな素数で割った余りを求める形式であれば、階乗の前計算が $O(N)$ でできていました。ただし今回は小数で求めるという都合上DP（パスカルの三角形）をしたため、前計算の計算量が $O(N^{2})$ になっています。他にも、合成数や大きくない素数で割った余りを答える場合など逆元が使えない時もパスカルの三角形を使うことがあります。