TopCoder SRM313 Div2 250Pts

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

組合せゲームという長方形の盤面で遊ぶソリティアを単純化したゲームがある。盤面はN個の正方形に連続して分けられる。正方形の中には1からNの整数が一つずつ入る。また、それぞれの正方形の位置にも数値が1からNまで左から順に振られている。ゲームは次のようなものである。まず、ある場所を一つ選ぶ。次にその場所に書かれている数字に飛ぶ。これを繰り返し、最初の位置に戻ったら終了とするというものである。ボードはboard[]という整数型の配列で与えられ、i番目の要素はi番目の正方形の位置に書かれている値である(iは1から始まる添え字とする)。ゲームのプレーヤーが正方形をもっとも多く飛んでいくときの、そのとんだ回数を返せ。

同じ場所に飛んで終了した場合は1回として数えることに注意。

私の解答はこちら。

public class CyclesInPermutations {

 public int maxCycle(int[] board) {
  int maxcycle = 0;
  for( int i=0 ; i<board.length ; i++ ){
   int startPos = i; // 初期位置
   int jumpTo = board[i]-1; // 飛んでいく先
   int nStep = 1;
   while( true ){
    maxcycle = Math.max(maxcycle, nStep); // とんだ回数の更新
    if( jumpTo == startPos ){ // 初期位置に戻ってきたら終了
     break;
    }
    jumpTo = board[jumpTo]-1; // 次に飛ぶ位置
    nStep++; // とんだ回数をカウント
   }
  }
  return maxcycle;
 }

}

得点は189.66/250、中央値は約199点。最初の位置に戻れば終了というところで、なぜか途中通った箇所に着いたら終了と考えていたので時間をくってしまいました。