TopCoder SRM399 Div2 250Pts

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

0からn-1まで番号をつけられた、環状の地下鉄の路線がある。駅0を出て、駅1に到着するのにt[0]という時間がかかる。同様に、駅1を出て駅2に到着するのにt[1]という時間がかかるし、駅n-1を出て駅0に到着するのにはt[n-1]という時間がかかる。駅と駅の間はどちらかの方向に向かってくことができる(訳注：時計回りと反時計回りをイメージしよう)。つまり、ある駅からある駅へ向かうのに、同じ駅を2回以上通らないで向かう方法は2通りあることになる。例えば4つ駅があるものとし、1から3へ向かうのであれば、1-2-3、あるいは1-0-3という向かい方があることになる。前者では移動時間の合計はt[1]+t[2]であり、後者はt[0]+t[3]になる。ある人が別の駅へ向かいたいと思っているとき、その人はいつも速く到着できる方を選ぶ。さて、t[]という移動時間の一覧が与えられたとき、2駅間の移動でどんなに速く動いても最も時間がかかってしまう駅のペアを求め、その移動にかかる時間を返すメソッドを作成せよ。

私の解答はこちら。

public class CircularLine {

 public int longestTravel(int[] t) {
  int[][] dist = new int[t.length][t.length];
  int[] tt = new int[t.length*2];
  for( int i=0 ; i<tt.length ; i++ ){
   tt[i] = t[i % t.length]; // tを2回繰り返したもの
  }
  for( int i=0 ; i<t.length ; i++ ){
   for( int j=0 ; j<t.length ; j++ ){
    // iからjへ向かう距離を計算
    int from = i;
    int to = j;
    if( j<i ){
     from = i;
     to = j + t.length;
    }
    for( int k=from ; k<to ; k++ ){
     dist[i][j] += tt[k];
    }
   }
  }

  int max = 0; // 2駅間の移動でもっともかかる時間
  for( int i=0 ; i<t.length ; i++ ){
   for( int j=i+1 ; j<t.length ; j++ ){
    int minDist = Math.min(dist[i][j], dist[j][i]); // 駅i～j間で最速の移動をしても
    max = Math.max(max, minDist); // 移動にかかる時間の最大値を更新してしまうか?を検討
   }
  }
  return max;
 }

}

得点は147.55/250、1回のsubmitでシステムテストクリア。中央値は約156点。2駅の移動は2次元配列で管理しています。dist[i][j]、dist[j][i]が駅iから駅jへ向かうという意味であり、それぞれ添え字の増える方向に向かった場合、減った方向に向かった場合の2種類の経路でかかる時間になります。したがってdist[i][j]とdist[j][i]のうち、小さい方がある人が選択するルートになります。添字操作が面倒なので、tを2回繰り返すことで、添え字が小さくなる方向への探索を簡単に置き換えることにしています。