TopCoder SRM470 Div2 250Pts

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

巡回しているセールスマンはLinear王国で製品を売ろうとしている。Linear王国は座標系にNの街がある。各街は点であり、i番目の街は(x[i], y[i])にある。Linear王国のすべての街は共線性がある、すなわちすべての街を通るまっすぐの線が存在することを意味する。巡回セールスマンはすべての街を訪問しようとしている。2つの街を移動するのに必要な距離はマンハッタン距離に等しい。任意の街から移動し、任意の街で移動を終えるとしたとき、セールスマンが移動しなければならない距離の最小値を返せ。

私の解答はこちら。

public class LinearTravellingSalesman {

 public int findMinimumDistance(int[] x, int[] y) {
  int[] minDist = {0, 0};
  boolean isStart = true;
  int[] prev = {0, 0};
  boolean[] isUsed = new boolean[x.length];
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && x[j] < minx ){
     target = j;
     minx = x[j];
    }
   }
   if( !isStart ){
    minDist[0] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }

  for( int i=0 ; i<x.length ; i++ ){
   isUsed[i] = false;
   isStart = true;
  }
  prev[0] = 0; prev[1] = 0;
  
  for( int i=0 ; i<x.length ; i++ ){
   int target = -1;
   int minx = 10001;
   for( int j=0 ; j<x.length ; j++ ){
    if( isUsed[j] == false && y[j] < minx ){
     target = j;
     minx = y[j];
    }
   }
   if( !isStart ){
    minDist[1] += ( Math.abs(x[target] - prev[0]) +  Math.abs(y[target] - prev[1]));
   }
   prev[0] = x[target];
   prev[1] = y[target];
   isStart = false;
   isUsed[target] = true;
  }
  
  return minDist[0] < minDist[1] ? minDist[0] : minDist[1];
 }

}

得点は183.36/250、1回のsubmitでシステムテストクリア。PCが壊れる前に解き、コメントがないので解き方の方針は忘れてしまいました(苦笑)