TopCoder SRM185 Div2 250Pts

英語の速読とJavaのトレーニング。今日の問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

問題について大まかに和訳する。進級試験について考える。進級試験に合格するには、全試験の合計点の65%以上の得点率が必要である。最終試験直前までの試験の点数(pointsPossible[])とそれぞれの試験で得た点数(pointsEarned[])（もちろん順番はpointsPossibleに対応している）、および最終試験の合計点(finalExam)が与えられたとする。このとき最終試験で何点得られれば合格になるかを返す関数を作成せよ。ただし、最終試験で最高点を取得しても合格できない場合は-1を返せ。

例えば、pointsEarned={1,2,3,4}、pointsPossible={2,3,4,5}、finalExam=7とする。試験の満点は21点(=2+3+4+5+7)であり、21*0.65=13.65を上回るには最終試験で4点を取ればよいので、4を返すように関数を作成すればよい。私の解答は以下の通りである。

public class PassingGrade {
 public int pointsNeeded(int[] pointsEarned, int[] pointsPossible, int finalExam) {
  int sumEarned = 0,sumPossible=0;
  for( int i=0 ; i<pointsEarned.length ; i++){
   sumEarned += pointsEarned[i];
   sumPossible += pointsPossible[i];
  }
  for( int i=0 ; i<=finalExam ; i++){
   if( (double)(sumEarned+i) / (sumPossible+finalExam)  >= 0.65 ){
    return i;
   }
  }
  return -1;
 }
}

得点は234.93/250と上位15%以内に入る高速解答。高速に解答できた一番の理由として、for文で何点とったら最大得点の0.65を超えるかという判定を書いたことがあるだろう。変に計算しなくて良いので、非常に問題が単純化された。ただし、これは問題設定でfinalExamの上限値が1から3000であり、高々3000回のループで終了するということで、特にスピードを意識しなくてもよいからである。finalExamの最高値が1000000程度になるのであれば、きちんと計算して65%になる点数を計算する必要があるだろう。