マツシタのお勉強

大ジャンプ AtCoder ABC 011D

問題

D: 大ジャンプ - AtCoder Beginner Contest 011 | AtCoder

解き方(満点解法)

以下のステップで解くことができる。

  1. 左右に移動する回数と上下に移動する回数の2パターンについて考える
  2. 左右に移動する回数をhorizon回と固定する
  3. すると上下に移動する回数はvertical = N - horizonとなる
  4. 左右のみの移動を考えた時に最終的にXにいる通り数を考えたい
  5. よって、右に移動する回数はright = (horizon + X) / 2と決定される
  6. 同様に、上下に移動する回数を考える。
  7. 上に移動する回数はup = (vertical + Y) / 2となる。
  8. 以上をまとめると、「全ての回数からhorizon回を選ぶ通り数」「horizon回からright回を選ぶ通り数」「vertical数からup回選ぶ通り数」をかけ合わせたものが、左右方向にhorizon回移動した時に、座標(X, Y)にいる通り数が得られる。
  9. 最後にhorizonは一時的に固定しただけなので、0~Nまでループさせる、足し合わせることでN回の操作で座標(X, Y)にいる通り数が得られる。

解説リンク AtCoder Beginner Contest 011 解説

コンビネーションはパスカルの三角形を用いて求める

keita-matsushita.hatenablog.com

注意点として、パスカルの三角形で保持する値はNが大きい値になるとLongの最大値を越してしまう。そこで、パスカルの三角形に、「その組む合わせが選ばれる確率」を持たせる。

nCk/2^n

となる。分母の「2」という数字はその要素を含むか否かの2通りを表している。

ソースコード