TopCoder SRM292 Div2 250Pts

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

高速道路が東西に延々と続いている。小心者のボブは直線に歩く。ボブの歩いたパスが与えられたとき、彼が何回道を渡ったかということが知りたい。ただし、彼が道でぶらぶらしていて、途中で元来た道を行った場合は、渡った回数として数えない。道は大したことのない幅なので、あるy座標を固定した水平線のように考えてよい。roadYという道の座標値とbobX[]、bobY[]というボブの通ったパスが引数として与えられるので、ボブが道を渡りきった回数を返すメソッドcrossingを作成せよ。bobX[]とbobY[]のi番目の要素がボブの通ったパスの座標になる。ボブは最初の位置から動きだし、次の点へ直線に動き、最後の点までそれを繰り返す。ボブは道の上で動き出したり、止まったりはしない。

例えば、roadY=6、bobX[]={3,7,9,2}、bobY[]={-3,8,8,2}とすると、2が答えになる。(3,-3)->(7,8)で6をまたぐので1回、(9,8)->(2,2)で6をまたぐので2回というカウントを行う。

私の解答はこちら。

public class FowlRoad {

 public int crossings(int roadY, int[] bobX, int[] bobY) {
  boolean isBobSouth = bobY[0]>roadY ? false : true; // ボブは南側にいるか?
  int nCross = 0;
  for( int i=1 ; i<bobY.length ; i++ ){
   if( bobY[i-1] >= roadY && bobY[i]<roadY && isBobSouth == false ){
    nCross++;
    isBobSouth = true;
   }else if( bobY[i-1] <= roadY && bobY[i]>roadY && isBobSouth == true ){
    nCross++;
    isBobSouth = false;
   }
  }
  return nCross;
 }

}

得点は218.14/250、中央値は約198点。提出後に気付いたのですが、if文に含まれている直前のi-1の情報はisBobSouthで管理しているので不要のはず。また、bobX[]というのは全く利用しないで回答ができる。気を付けるのは、渡りきったということを表現する方法でしょう。ちょうど道の上に乗って、そこから折り返すか進むかでカウントするしないが決まるので、その処理を誤らないことが肝心。