TopCoder SRM207 Div2 250Pts

今日のTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。

あなたは公共交通機関の勉強をしており、ある道を毎分何台のバスが通っているかを知りたい。そこで、車でその道を通り、何台のバスに出会うか、もしくは追い越したかということを数えたい。ここでは、仮定として道は直線で、バスはすべて車と同じ方向に走るものとする。

車の速さをspped(単位はメートル/秒)、車が動き出す瞬間にi番目のがバス何メートル先にいるかを表すpositions[]、i番目のバスの速さvelocities[](単位はメートル/秒)、計測期間timeが与えられたときに、t計測時間中に何台のバスに出会うかを返すメソッドを作成せよ。ただし、最初同じ位置にいるバスは出会ったとするようにせよ。

私の解答はこちら。

public class TransportCounting {
 public int countBuses(int speed, int[] positions, int[] velocities, int time) {
  int met = 0;
  for( int i=0 ; i<positions.length ; i++ ){
   if( positions[i] == 0 ) met++; // 最初の位置が同じ
   else if( speed*time >= positions[i]+velocities[i]*time ) met++; // 途中で追いついた
  }
  return met;
 }

}

得点は242.79/250。中央値は172点程度。最初の位置が同じということを明示的に条件に加えないと間違いになる(最初のif文のこと)。例えば、最初同じ位置で測定を開始し、バスの方が車よりも速い場合、車とバスは以後出会わなくなるので、カウントに失敗するのである。