TopCoder SRM411 Div2 250Pts

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

ボニーは好きな数学の授業で、非負の整数には、二つの非負の整数の2乗和で表されるものがあるということを習った。例えば、13=2*2+3*3という具合である。ボニーはのちに、そのような数が2通り以上の分割方法があるということを発見した。例えば25=0*0+5*5=3*3+4*4ということである。ボニーは整数に対し、異なる非負の整数の二乗和で表されるパターンの数を得点と定義することにした。二つの二乗の数を足す順序は異なっても同じものと扱う。これにより、25のスコアは2、2のスコアは1となる(2=1*1+1*1)。また、1のスコアは1、0のスコアは1となる。ボニーは以下の問題を解くのにあなたの手伝いを必要としている。ボニーはlowerBound以上、upperbound以下の整数でスコアが最大となる整数を見つけたいというのである。もし、複数の整数が最高スコアになった場合は、それらの数の中で最大になるようなものを求めるようにせよ。

私の解答はこちら。

public class MaximumScoredNumber {

 public int getNumber(int lowerBound, int upperBound) {
  int largest = lowerBound; // スコアが最大になる整数
  int maxscore = 0; // スコアの最大値
  for( int num=lowerBound ; num <= upperBound ; num++ ){
   int score = 0;
   int range = (int)Math.sqrt(num) + 1;
   for( int i=0 ; i<range ; i++ ){
    for( int j=i ; j<range ; j++ ){ // j=iからにすることで、順序が違うだけの計算を省ける
     if( i*i + j*j == num ) score++;
    }
   }
   if( score >= maxscore ){ // スコアが現在の値に並ぶか超えたら更新
    maxscore = score;
    largest = num;
   }
  }
  return largest;
 }

}

得点は238.06/250、1回のsubmitでシステムテストクリア。中央値は約151点。