TopCoder SRM384 Div2 250Pts

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

ジェーンは最高の体型を維持しようとしている。ジェーンの姉はそのことを知っているので、ジェーンにいたずらをすることにした。ジェーンの古い目盛りを破棄したのちに、本当の体重に代わり体重の二乗を示す目盛りを用意した。その変化に気付かず、ジェーンはしばらくその目盛りを使い続けていた。そしてある朝、"うわっ、私apparentGainポンドも太った!"と叫んだ。apparentGainという本当の体重と以前の体重の二乗の差が与えられたとき、ジェーンの現在の体重であり得る値を、昇順にして整数型の配列として返せ。体重は1以上の整数とする。

一見問題文が分かりにくいのだが、体重は整数の値をとり得るわけで、現在の体重をcw、以前の体重がpwという整数であったときにcw*cw-pw*pw=apparentGainになるようなcwは何かということを聞いているのである。私の解答は以下の通り。

import java.util.ArrayList;
import java.util.Arrays;

public class Prank {

 public int[] realWeight(int apparentGain) {
  ArrayList<Integer> aList = new ArrayList<Integer>();
  // apparentGainが1～100000ということから、過去の体重の探索範囲が
  // およそ現在の体重-searchから現在の体重-1でよいことになる。
  // 例えば現在の体重が10000で過去の体重が100ということはあり得ない。
  long search = (long)Math.sqrt(100000)+1;
  for( long i=1 ; i<=apparentGain/2+1 ; i++ ){ // iが現在の体重
   long start = Math.max(1, i - search);
   for( long j=start ; j<=i ; j++ ){ // jは過去の体重
    if( i*i - j*j == (long)apparentGain ){ // きっちりapparentGainだけ違っていれば
     // System.out.println(i);
     aList.add((int)i); // 解に加える
    }
   }
  }
  // System.out.println("-" + aList.size());
  int[] ret = new int[aList.size()];
  for( int i=0 ; i<aList.size() ; i++ ){
   ret[i] = aList.get(i);
  }
  Arrays.sort(ret);
  return ret;
 }

}

この問題では探索範囲をあらかじめ狭めておかないと2秒という制約にひっかかってしまいます。単なる二重ループなのですが、いくらか工夫が必要です。現在の体重の最大値はapparentGain/2+1程度で評価できます。それより大きい値では過去の体重が現在の体重-1としても、apparentGainを超えてしまうためです。例えばapparentGainが5のとき現在の体重は1～3までです。現在の体重を4とすると、4よりわずか1小さい3を過去の体重としても4^2-3^2 = 7 > 5なので、やはり解にはなりえません。

得点は164.37/250、1回のsubmitでシステムテストクリア。表示込みで200msecかかるケースもあるので、時間はギリギリ。中央値は約123点でした。