No Caffeine, No Life

プログラミング(主にPython)

ABC 011 D:大ジャンプ 組み合わせ・順列の計算

問題:

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

解説:

目的地{\displaystyle (X, Y) }{\displaystyle D }で規格化する。すると、{\displaystyle N }回のうち、{\displaystyle X }方向、{\displaystyle Y }方向に正味でどれだけ動けばよいかが、まず求められる。

  • {\displaystyle X }方向に動く回数を{\displaystyle u }方向
  • {\displaystyle Y }方向に動く回数を{\displaystyle v }方向
  • と、おくと、{\displaystyle u + v = N }

ここで、{\displaystyle u, \ v }{\displaystyle x, \ y }と、異なっていてよい。というのも、負方向への移動が可能なので、行きすぎたら戻ってきて、ということもありえるから。ただし、そのために{\displaystyle u }{\displaystyle x }、または{\displaystyle v }{\displaystyle y }の差は必ず偶数で無いといけない。

最後に、組み合わせ(combination。いわゆる{\displaystyle _{n} C _{r} })を計算する。ここでは、ガンマ関数の自然対数(lgamma)を経由して、計算している。

※ガンマ関数については、

ガンマ関数(階乗の一般化)の定義と性質 | 高校数学の美しい物語

を参照。

解答例:

広告を非表示にする