TopCoder SRM382 Div2 250Pts

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

整数型の配列が与えられたときに、要素数がK以上かつ、平均が最大になる連続した部分列を見つけ、(0-basedで)その位置を要素2の配列で返すメソッドを作成せよ。もし、そのようなものが複数ある場合は、長さが最大になるもの、それでも複数候補がある場合は、一番最初に登場した部分列の位置を返すようにせよ。

私の解答はこちら。

public class ContiguousSubsequences {

 public int[] findMaxAverage(int[] a, int K) {
  int[] ret = new int[2];
  double maxave = 0.0;
  int maxlen = 0;
  for( int i=0 ; i<a.length ; i++ ){
   for( int j=0 ; j<a.length ; j++ ){
    if( j-i+1 < K ) continue; // 要素数がKに満たない場合は考えない
    double ave = average(a, i, j);
    int len = j-i+1;
    if( ave > maxave ){ // 最大値が更新された場合
     maxave = ave;
     ret[0] = i;
     ret[1] = j;
     maxlen = len;
    }else if( ave == maxave ){ // 最大値に一致した場合
     if( len > maxlen ){ // 長さが以前のものより長い場合
      ret[0] = i;
      ret[1] = j;
      maxlen = len;
     }
    }
   }
  }
  return ret;
 }

 // 添字がfromからtoまでの要素の平均を計算する
 private double average(int[] a, int from, int to){
  double ret = 0.0;
  for( int i=from ; i<=to ; i++ ){
   ret += a[i];
  }
  return ret/(to-from+1);
 }

}

得点は214.46/250、1回のsubmitでシステムテストクリア。PracticeRoomの中央値は約135点、SRM当日の正解率は約65%。平均が同じときに最大長を更新するというロジックを入れずに悩むこと数分。