三井住友信託銀行プログラミングコンテスト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回を加えれば答えになる。