TopCoder SRM463 Div2 250Pts

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

タロウとハナコはバニーパズルで遊んでいる。1列にウサギが何匹か並んでいて、各ウサギの位置はbunnies[](昇順にソート済)という整数型配列で与えられている。ウサギは次のように1度だけ振る舞う:aとbの位置にいるウサギAとBを選ぶ。AはBを飛び越え2*b-aの位置に飛ぶ。もしその位置にウサギが既にいれば飛ぶことはできない。複数匹のウサギを飛び越えることもできない。以上の条件が成り立つとき、AとBの選び方の総数を返せ。なおAがBを飛び越えるのと、BがAを飛び越えるのは異なるものとする。

私の解答はこちら。

public class BunnyPuzzle {

 public int theCount(int[] bunnies) {
  int n = 0;
  // 左のウサギがその右の位置にいるウサギを飛び越える
  for( int i=0 ; i<bunnies.length ; i++ ){
   if( i == bunnies.length-2 ){ // 一番右の2匹の組は成立するペア
    n++;
    break;
   }
   int cur = bunnies[i];
   int tar = bunnies[i+1];
   int jumpto = bunnies[i] + 2 * (tar - cur);
   if( jumpto < bunnies[i+2] ) n++;
  }
  // 右のウサギがその左の位置にいるウサギを飛び越える
  for( int i=bunnies.length-1 ; i>=1 ; i-- ){
   if( i==1 ){ // 一番左の2匹の組は成立するペア
    n++;
    break;
   }
   int cur = bunnies[i];
   int tar = bunnies[i-1];
   int jumpto = bunnies[i] + 2 * (tar - cur);
   if( jumpto > bunnies[i-2] ) n++;
  }
  return n;
 }

}

得点は166.60/250、1回のsubmitでシステムテストクリア。全部の組を探索する必要はなく、隣り合う2匹に着目するのが簡単と気付くまでちょっと時間がかかりました。