TopCoder SRM172 Div2 250Pts

昨日のJavaと英語の練習。問題の詳細はこちらより確認できる(要TopCoder登録)。

問題を大雑把に和訳すると以下のようになる。

縄跳びを二人でする。このときできるだけ身長heightの人と同じ身長の人をパートナーにしたい。candidates[]からheightに近い身長順に、候補者二人の身長を取り出し、二人の身長は昇順にして返せ。ただし、heightとの身長差(絶対値だよ!)が同じになった候補者が複数現れた場合は、背の高い方の優先順位を上にせよ。また、candidates[]は同じ身長の値が何度も現れる可能性がある。

例えばcandidates[] = {169,170,166,172},height=168とした場合は{169,170}が回答になる。169は文句なしに選ばれる。166と170は両方ともheight=168との身長の差は2であるが、身長の高い方を優先するためである。

Javaで実装したサンプルはこちら。点数は112.55と大苦戦。

public class SkipRope {
 public int[] partners(int[] candidates, int height) {
  Arrays.sort(candidates);
  int first=-1; // 1番heightに近い人の身長
  int second=-1;
  int firstDiff=100000; // heightとの差の絶対値
  int secondDiff=100000;
  int diff;
  for( int i=0 ; i<candidates.length ; i++){
   diff = Math.abs(candidates[i]-height);
   if( Math.abs(diff) <= firstDiff ){ // 1番height近い人が現れた場合
    secondDiff = firstDiff; // 1番近いのは2番目に移り、
    second = first;
    firstDiff = diff; // 1番目に新たにデータを入れる
    first = candidates[i];
   }else if( Math.abs(diff) <= secondDiff ){
    secondDiff = diff; // 1番heightに近くないが、2番目にheightに近い人が現れた場合
    second = candidates[i];
   }
  }
  int[] result = new int[]{first,second};
  Arrays.sort(result);
  return result;
 }
}

ポイントになるのは初めて知ったArrays.sort()。このメソッドによってcandidatesが昇順にソートされるので、candidatesを先頭から順番に見ていき、heightとの身長差が同じになった場合はあとの方に現れた方を優先度の高い候補者にすれば、身長の高い方が自動的に選ばれるということである。

最初はソートのメソッドを知らず、見せられないよ～というコードを書いていたので、思いの他時間がかかってしまった。2部リーグの正解率も41%台とかなり難問の部類になるようだ。調べてみると、この問題よりも正答率が低かった2部リーグの第1問は、過去出題された約350題のうちわずか9題だった。

上記の内容を補足すると、TopCoderは2部リーグ制をとっている。75分で3問解くルールで、1問目から3問目まで順に難しくなるようにできているのである。