TopCoder SRM267 Div2 250Pts

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

最低10万ドル以上の課税可能な人の2004年の税金は以下のテーブルから計算される(表は問題文中を参照)。あなたの税金を計算するために、課税対象収入と税率と控除の適切なグループを見つけよ。

誰かがいくら税金を払うか分かった時、元の課税対象の収入はいくらだったのかということが知りたい。taxAmountという課税された額が引数として与えられたときに、もとの課税対象収入のもっとも近い額を返すTaxTableというメソッドを作成せよ。結果は最も近いドルの値で返せ(つまり小数点第1位で四捨五入)。もし、taxAmountが小さすぎて、テーブルになければ-1を返すようにせよ。

私の解答はこちら。

public class TaxTable {

 public int income(int taxAmount) {
  int max = (1000000 + 25357)*20 / 7 + 1; // 入力の上限から分かる探索範囲の上限
  int ret = -1;
  int least = 25000 - 6525; // 入力の下限を計算
  if( taxAmount < least ){
   return -1;
  }
  double minDiff = Double.MAX_VALUE;
  // 入力の下限から上限までで誤差が最小になる収入額を計算
  for( int i=100000 ; i<=max ; i++ ){
   double mul = retMultiplier(i);
   double sub = retSubtraction(i);
   double diff = Math.abs((i*mul-sub)-taxAmount);
   if( diff < minDiff ){
    minDiff = diff;
    ret = i;
   }
  }
  return ret;
 }
 private double retMultiplier(int v){ // 課税対象額に応じた税率
  if( v>=100000 && v<117250 ){
   return 0.25;
  }else if( v<178650 ){
   return 0.28;
  }else if( v<319100 ){
   return 0.33;
  }else{
   return 0.35;
  }
 }
 private double retSubtraction(int v){ // 課税対象額に応じた控除額
  if( v>=100000 && v<117250 ){
   return 6525.0;
  }else if( v<178650 ){
   return 10042.50;
  }else if( v<319100 ){
   return 18975.0;
  }else{
   return 25357.0;
  }
 }
}

得点は126.90/250。毎回300万回程度のループが回っているので、あまり速い動作にはならないと思います。TopCoderでは2秒で結果が返ってこればOKで、目安としては1000万回のループ以下であればOKということになるそうです。入力の上限がない場合は工夫が必要とは思いますが、コンテストで簡単な部類の問題なのでそこまで考えなくても良いようにできているのだと思います。