yukicoder No.1139 Slime Race

問題

数直線上に、スライムがN匹いて、i番目のスライムは、時刻0で、座標x_i、速さv_i(正の方向)でいる。

この数直線上で、同じ座標になる場合は、「衝突」し、以下のようになる。

• 番号が小さいスライムがその他のスライムをすべて吸収し、吸収されたスライムは消滅
• 吸収したスライムは、自分自身の速さ＋吸収したスライム速さの和、の速度になる

ここで、すべてのスライムについて、時刻0から時刻tまでに走った距離の合計をf(t)とする。吸収され消滅したスライムはその時点で走るのを終了したとみなす。

f(T) >= Dとなる最小の整数Tを求めよ。

制約

• 1 <= N <= 10^5
• 1 <= D <= 10^9
• 1 <= x_i, v_i <= 10^9
• i < jならばx_i < x_j

解法

シミュレーションや二分探索では難しい。
そこで、吸収の前後について考える。

あるスライムa,bがt_1で衝突し、t_2まで進む場合を考えると、合計移動距離は、
v_a * t_1 + v_b * t_1 + (v_a + v_b) * t_2
になる。
展開すると、v_a * (t_1 + t_2) + v_b * (t_1 + t_2)になるので、結局、吸収されないで進んだ場合と同じになることがわかる。

したがって、吸収は無視して考えてよいので、結局f(T)はT * すべてのスライムの速度の和v_sum、となり、これがD以上になるTは、切り上げの式から、
T = (D + (v_sum-1)) / v_sum
となる。