大ジャンプ AtCoder ABC 011D
問題
D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder
解き方(満点解法)
以下のステップで解くことができる。
- 左右に移動する回数と上下に移動する回数の2パターンについて考える
- 左右に移動する回数を
horizon
回と固定する - すると上下に移動する回数は
vertical = N - horizon
となる - 左右のみの移動を考えた時に最終的にXにいる通り数を考えたい
- よって、右に移動する回数は
right = (horizon + X) / 2
と決定される - 同様に、上下に移動する回数を考える。
- 上に移動する回数は
up = (vertical + Y) / 2
となる。 - 以上をまとめると、「全ての回数からhorizon回を選ぶ通り数」「horizon回からright回を選ぶ通り数」「vertical数からup回選ぶ通り数」をかけ合わせたものが、左右方向にhorizon回移動した時に、座標(X, Y)にいる通り数が得られる。
- 最後にhorizonは一時的に固定しただけなので、0~Nまでループさせる、足し合わせることでN回の操作で座標(X, Y)にいる通り数が得られる。
解説リンク AtCoder Beginner Contest 011 解説
コンビネーションはパスカルの三角形を用いて求める
keita-matsushita.hatenablog.com
注意点として、パスカルの三角形で保持する値はNが大きい値になるとLongの最大値を越してしまう。そこで、パスカルの三角形に、「その組む合わせが選ばれる確率」を持たせる。
nCk/2^n
となる。分母の「2」という数字はその要素を含むか否かの2通りを表している。