No Caffeine, No Life

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

ABC 034 C:経路 組み合わせ・順列の計算

問題:

C: 経路 - AtCoder Beginner Contest 034 | AtCoder

解説:

 高校数学で習う公式を当てはめれば、求めたいのは{\displaystyle _{H+W-2} C _{H-1 } }とわかる。

道順の場合の数を求めるテクニック | 高校数学の美しい物語

ここでは、組み合わせの計算をするために逆関数を用いたかたちをとっている。

なお、pythonにおけるpow関数は、組み込み関数とmathモジュールにある関数の2つがある。このうち、pow(X, Y, Z)と3つの引数を取るのは組み込み関数の方なので注意が必要:

pow(xy[z])(原文)

x の y 乗を返します; z があれば、x の y 乗に対する z の剰余を返します (pow(x, y) % z より効率よく計算されます)。二引数の形式 pow(x, y) は、冪乗演算子を使った x**y と等価です。

引数は数値型でなくてはなりません。型混合の場合、二項算術演算における型強制規則が適用されます。 int 被演算子に対しては、第二引数が負でない限り、結果は (型強制後の) 被演算子と同じ型になります; 負の場合、全ての引数は浮動小数点に変換され、浮動小数点の結果が返されます。例えば、 10**2 は 100 を返しますが、 10**-2 は 0.01 を返します。第二引数が負の場合、第三引数は省略しなければなりません。 zがある場合、 x および y は整数型でなければならず、 y は非負でなくてはなりません。

一方で、mathモジュールの方は、

math.pow(xy)(原文)

x の y 乗を返します。例外的な場合については、 C99 標準の付録 ‘F’ に可能な限り従います。特に、 pow(1.0, x) と pow(x, 0.0) は、たとえ x が零や NaN でも、常に 1.0 を返します。もし x と y の両方が有限の値で、 x が負、 y が整数でない場合、 pow(x, y) は未定義で、 ValueError を送出します。

組み込みの ** 演算子と違って、 math.pow() は両方の引数を float 型に変換します。正確な整数の冪乗を計算するには ** もしくは組み込みの pow() 関数を使ってください。

 

解答例: