TopCoder SRM243 Div2 250Pts

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

あなたはいくつかアルゴリズムのテストをしており、一番早いものを見つけたいと思っている。アルゴリズムの計算量というのは、三つからなる。constant、power、logPowerである。これらは配列で与えられており、i番目のアルゴリズムは、次式で与えられる。

constant[i]*N^power[i]*log(N)^logPower[i]

上の3つの配列と、サイズを表すNが与えられたときに最も速い(計算量が少ない)アルゴリズムのインデックスを返せ(先頭は0から始まるものとして)。タイのものがある場合には、インデックスが最も小さいものを返せ。

私の解答はこちら。

public class ComputationalComplexity {
 public int fastestAlgo(int[] constant, int[] power, int[] logPower, int N) {
  // こういう風に定義するのもあり。こちらを利用する場合、int i=0からループを開始することになる。
  // 解答の美しさを考慮すると、minはコメントにあるものの方が好きです。
  // double min = Double.POSITIVE_INFINITY;
  double min = constant[0]*Math.pow(N, power[0])*Math.pow(Math.log(N),logPower[0]);
  int idx = 0;
  for( int i=1 ; i<constant.length ; i++ ){
   double ith = constant[i]*Math.pow(N, power[i])*Math.pow(Math.log(N),logPower[i]);
   if( ith < min ){
    idx = i;
    min = ith;
   }
  }
  return idx;
 }
}

得点は205.78/250。数式をコードに落とすのに間違いがあり、解答にやや時間がかかってしまった。次の問題はSRM182 Div2 300Ptsと同じなので省略。