TopCoder SRM405 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

下降階乗をnからk個取るとき、その値はn*(n-1)*...*(n-k+1)と定義される。これをn^^kと表記することにする。例えば7^^3=7*6*5=210であるし、n^^1=nである。次にこの定義を非正の整数kに対して拡張する。そのために(n-k)*(n^^k)=n^^(k+1)という事実を用いる。つまり、n^^k=(n^^(k+1))/(n-k)となる。これにより、以下のことが分かる。

• n^^0=n^^1/(n-0)=1
• n^^(-1)=n^^0/(n+1)=1/(n+1)
• n^^(-2)=1/(n+1)/(n+2)
• より一般にはn^^(-k)=1/(n+1)/(n+2)/.../(n+k)

例えば3^^(-1)=1/4=0.25などとなる。nとkが与えられたとき、下降階乗をnからk個を取ったときの値を返すメソッドを作成せよ。

私の解答はこちら。kの値で分岐して計算しています。

public class FallingFactorialPower {

 public double compute(int n, int k) {
  if( k==0 ){
   return 1.0;
  }else if( k>0 ){
   double ret = 1.0;
   for( int i=0 ; i<k ; i++ ){
    ret *= (n-i);
   }
   return ret;
  }else{
   double ret = 1.0;
   for( int i=0 ; i<Math.abs(k) ; i++ ){
    ret /= (n+i+1);
   }
   return ret;
  }
 }

}

得点は237.85/250、1回のsubmitでシステムテストクリア。中央値は約205点。