phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

三井住友信託銀行プログラミングコンテスト2019 F. Interval Running

問題

高橋くんと青木くんは、直線上を同じスタート地点から走り出す。
同じ方向に向かって、

  • 高橋くんは、T1分を分速A1メートル、次のT2分を分速A2メートル、これを交互に繰り返す
  • 青木くんは、T1分を分速B1メートル、次のT2分を分速B2メートル、これを交互に繰り返す

高橋くんと青木くんは何回で会う(同じ位置にそろう)か?
スタート地点にいるときを除いた回数を答えよ。
無限回会う場合はinfinityを返せ。

制約

  • 1 <= T1, T2 <= 10^5
  • 1 <= A1, A2, B1, B2 <= 10^10
  • A1 != B1
  • A2 != B2

解法

高橋くんの位置と青木くんの位置の2つの変数があり扱いにくいので、二人の相対距離に注目する。
T1分の間は相対速度V1=(A1-B1)で、T2分の間は相対速度V2=(A2-B2)になっている。


場合分けで、もし「V1>0かつV2>0」または「V1<0かつV2<0」だった場合は、どんどん離れていってしまうため、二度と合わないので、0回。

「V1 * T1 + V2 * T2 == 0」となる場合は、T1+T2分ごとに出会うので、無限回会う。

それ以外の場合は、縦軸に相対距離、横軸に時間をとったグラフで「横軸と交差する回数」が答えになる。

相対距離W1 = V1 * T1と相対距離W2 = V1 * T1 + V2 * T2を考えると、W2だけ毎回位置がずれていくので、W1が横軸と交わるまで減らす回数を数えればよい。
W2がW1と同じ符号の場合は、横軸と交わらないので0回。
それ以外は、交わる回数は、2*abs(W1)/abs(W2)で求められるが、割り切れる場合最後に会うのは1回になることに注意。
これに、最初の横軸と交わる1回を加えれば答えになる。