TopCoder SRM252 Div2 250Pts

今日の問題はなぜか検索をかけても出てこないのでリンクは省略。それでは、問題について説明する。

山の離れた地域で交戦中の一族がいる。軍隊をよりよい組織にするために、N個の前哨基地を丘に沿ってまっすぐに建てた。各前哨基地は怪しい動きの監視と、非常事態には知らせを広める役割がある。一旦基地が警報を受け取ると、メッセンジャーは継続的にアルプフォンを吹き、他の基地に警報を知らせる。二つの隣り合う基地に音が届くのに、ちょうど1単位の時間がかかる。ある基地と最も近い警報源からの距離がxだけ間が離れていれば、x単位時間音が届くのに時間がかかるということになる。

いくつかの基地が刑法を鳴らしたとしよう。あなたは、その他のすべての基地が知らせを受け取るのに何単位時間かかるかということを決めるのが課題である。outposts[]というN個の基地の状態を表す文字列が引数で与えられる。i番目の文字がi番目の基地であり、xという文字が警報を、-が静かな状態を表すものとする。

例えば、"--x-x---"であれば、3を返す。これは一番右の-にxからの警報が届くのに3単位時間かかるからである。

私の解答はこちら。

public class WarCry {
 public int alertTime(String outposts) {
  char[] line = outposts.toCharArray();
  int[] dist = new int[line.length];
  // とりうる距離の最大値は配列の長さ-1なので、それ以上に大きい値で初期化
  for( int i=0 ; i<dist.length ; i++ ){
   dist[i] = dist.length;
  }
  // 各xからの距離(インデックスの差)を計算する
  // xが出てきたときが更新するタイミングになる
  // ループの中で距離は最小値に更新されていく。
  for( int i=0 ; i<line.length ; i++ ){
   if( line[i] == 'x' ){
    for( int j=0 ; j<line.length ; j++){
     int tmpDist = Math.abs(i-j);
     if( tmpDist < dist[j] ){
      dist[j] = tmpDist;
     }
    }
   }
  }
  // 全体で最も警報源から離れている場所を調べる
  int maxDist = -1;
  for( int i=0 ; i<dist.length ; i++ ){
   if( dist[i] > maxDist ) maxDist = dist[i];
  }
  return maxDist;
 }
}

得点は220.84/250。xが出るたびに何度も更新しないといけないので、もう少しうまくかけないかなと思いました。一番簡単な解答ではあると思います。