TopCoder SRM285 Div2 250Pts

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

リンゴが入ったカゴを持っている。以下の手続きによって残っているリンゴの数を最大化したい。まず、いくつかのカゴを捨てる。そして、残ったカゴのリンゴの数が同じでなかったら、余分なリンゴをカゴから取り除く。

apples[]というi番目の要素がi番目のカゴの中にあるリンゴの数を表す整数型の配列があったときに、上記の手続きを実行して最大化されたリンゴの数がいくつになるかを求めて返すメソッドを作成せよ。

例えば{1, 2, 3, 4}という配列が与えられたら、6が答になる。リンゴを一切取り除かないと1*4=4、1だけを除くと2*3=6、1と2だけを除くと3*2=6、1と2と3を除くと4となるからである。

私の解答はこちら。

import java.util.Arrays;

public class BasketsWithApples {

 public int removeExcess(int[] apples) {
  Arrays.sort(apples); // ソートしておく
  int max = 0;
  if( apples.length == 1) return apples[0];
  for( int i=0 ; i<apples.length-1 ; i++ ){
   int sum = apples[i]*(apples.length-i);
   int comp = apples[i+1]*(apples.length-i-1); // 不要
   max = Math.max(max, sum);
   max = Math.max(max, comp); // 不要
  }
  return max;
 }

}

得点は124.67/250、中央値は227点。iをapples.length-1までループするようにすれば、実はcompに関連する2行は不要というオチに気付きました。道理で平均点が高くなるわけです。