TopCoder SRM286 Div2 250Pts

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

うっかりものがフェンスを作るためにいくつもの種類の棒を地中に埋めてしまった。同じ長さにするべきなのだが、違う長さに切られてしまったのである。そこでオーナーは同じ長さにするだけでなく、できるだけ棒を長くしたいと思っている。やることは最も長い棒を切って、もっとも短いものにくっつけるということである。このために、まず棒を短い方から順に並び替えて以下のことを行う。

• もっとも長い棒を棒の平均の長さになるように1回だけ切る
• 切ったものをもっとも短い棒の上にくっつける
• 棒を長さで再度ソートして、最初のステップに戻って、すべての棒の長さが同じになるまで繰り返す。

棒の長さを表すpole[]という整数型の配列が与えられたときに、すべての棒の長さが同じになるまで何回上記アルゴリズムが実行されるかを求めて返すメソッドを作成せよ。なお、poles[]の平均値は必ず整数になるものとする。

私の解答はこちら。

import java.util.Arrays;

public class CuttingPoles {

 public int countCuts(int[] poles) {
  int nProcedure = 0;
  while( true ){
   Arrays.sort(poles);
   if( poles[0] == poles[poles.length-1]) break; // 終了条件は最小と最大が同じになったとき
   int ave = average(poles);
   int diff = poles[poles.length-1]-ave; // 継ぎ接ぎする棒の長さ
   poles[0] += diff; // 棒を接ぐ
   poles[poles.length-1] -= diff; // 棒を短くする
   nProcedure++;
  }
  return nProcedure;
 }
 private int average(int[] array){ // 配列の平均を求めるメソッド
  int sum = 0;
  for( int i=0 ; i<array.length ; i++ ){
   sum += array[i];
  }
  return sum/array.length;
 }
}

得点は240.86/250、中央値は約208点。上のコードは汚いので改良するとこんな感じ。

import java.util.Arrays;

public class CuttingPoles {

 public int countCuts(int[] poles) {
  int nProcedure = 0;
  int nPoles = poles.length; // 繰り返し利用する値は定数扱いする
  int ave = average(poles);
  while( true ){
   Arrays.sort(poles);
   if( poles[0] == poles[nPoles-1]) break;
   int diff = poles[nPoles-1]-ave;
   poles[0] += diff; 
   poles[nPoles-1] -= diff;
   nProcedure++;
  }
  return nProcedure;
 }
 private int average(int[] array){
  int sum = 0;
  for( int i=0 ; i<array.length ; i++ ){
   sum += array[i];
  }
  return sum/array.length;
 }
}

lengthメソッドも繰り返し利用することで遅くなるので、その辺を中心に改良してみました。