TopCoder SRM290 Div2 250Pts

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

ジョニーは偉大なプログラマになりたいので、いつもプログラミングスキルを改良しようと練習している。ジョニーはより速くタイピングができるようになれば、時間が節約できると思っている。速いタイピングの鍵はリズムを保つ、すなわち一定の時間間隔でキーをたたくということであると言われている。ジョニーのような多くのプログラマーは統計が大好きなので、タイピングプロセスを測るプログラムを書いた。プログラムはlettersというタイピングした文字列と、times[]という整数型の配列で、何ミリ秒でキーを押したかという情報を受け取る。times[]のi番目の要素は、lettersのi番目の要素のキーをたたいた時間である。どのキーも1度しか叩かれておらず、timesの内容は練習セッションを始めてからの時間になる。この問題を特に当たり、1つのキーを叩くのにかかる時間は整数であると仮定する。あなたへの課題はジョニーがタイピングするのに平均時間以上かかった文字を求めることである。これにより、ジョニーはそれらの文字のタイピングをより練習することができる。タイピングで平均以上タイプにかかった文字を入力のlettersの順序ですべて出力せよ。

私の解答はこちら。

public class SpeedTyper {

 public String lettersToPractice(String letters, int[] times) {
  int ave = average(times); 
  StringBuffer sb = new StringBuffer();
  int[] t = takenTimes(times);
  for( int i=0 ; i<t.length; i++ ){
   if( t[i] > ave ) sb.append(letters.charAt(i)); // 平均以上なら文字列の後ろに追加
  }
  return sb.toString();
 }
 private int average(int[] t){ // 配列の平均値を計算して返す
  int total = t[0];
  int len = t.length;
  for( int i=1 ; i<len ; i++ ){
   int tmp = t[i] - t[i-1];
   total += tmp;
  }
  return total/len;
 }
 private int[] takenTimes(int[] t){ // 配列の隣り合う要素の差分をとった結果を返す
  int len = t.length;
  int[] ret = new int[len];
  ret[0] = t[0];
  for( int i=1 ; i<len ; i++ ){
   ret[i] = t[i] - t[i-1];
  }
  return ret;
 }
}

得点は226.34/250、中央値は約219点。実は平均を求めるメソッドが無駄ということに気付いて愕然としました。ave=times[letters.length-1]/times.length;でOKだったのですね。