E - 直線コースの追い越し / Overtaking on a Straight Course Editorial by admin
gemini-3.5-flash-highOverview
This problem asks us to find the total number of times Takahashi and Aoki “overtake” each other while running at different speeds along a straight course, stopping at water stations along the way.
We will precisely count the moments when the sign of the difference between their positions (i.e., who is ahead) changes using an event sort (simulation) with integer arithmetic only, thereby eliminating floating-point errors.
Analysis
1. Definition and Determination of “Overtaking”
Let \(f(t)\) be Takahashi’s position at time \(t\), and \(g(t)\) be Aoki’s position. If we define the difference between their positions as \(D(t) = f(t) - g(t)\), overtaking corresponds to the sign of \(D(t)\) changing from positive to negative, or from negative to positive.
If the state \(D(t) = 0\) (both are at the same position) continues for some time and then their relative order changes, it is counted as \(1\) overtake. However, if they return to their original relative order without swapping, it is not counted as an overtake.
2. Avoiding Floating-Point Errors (Most Important)
The time from when Takahashi starts until he arrives at water station \(i\) is the distance run \(i\) divided by his speed \(V\), plus the total stopping time at the water stations up to that point.
If calculated naively, fractions like \(\frac{i}{V}\) will appear. Handling these with real number types such as float or double in the program will lead to incorrect determinations due to rounding errors (especially since the constraint \(N \le 5 \times 10^5\) is large, tiny errors can be fatal).
Therefore, we scale the time and position by \(V \times W\).
- Takahashi’s original speed is \(V\), and Aoki’s original speed is \(W\).
- If we scale time by \(V \times W\), their “speeds while running” become:
- Takahashi’s speed: \(V \times (V \times W) \rightarrow\) In the original world, Takahashi travels distance \(1\) in time \(1/V\). In the world where time is scaled by \(V \times W\), the (scaled) time required to travel the distance of \(1\) between water stations is \(W\).
- Aoki’s speed: \(W \times (V \times W) \rightarrow\) Similarly, the time required to travel the distance of \(1\) between water stations is \(V\).
- This allows us to represent the times at which all events occur as integers.
Concrete Time Conversion
Let \(A_i\) be Takahashi’s original arrival time at water station \(i\), and \(B_i\) be his original departure time (let the prefix sum of stopping times be \(P_R\)). $\(A_i = \frac{i}{V} + P_R[i-1]\)\( \)\(B_i = A_i + R_i\)$
The times \(A'_i, B'_i\) scaled by \(V \times W\) are as follows, and all can be calculated using integers: $\(A'_i = i \times W + (V \times W) \times P_R[i-1]\)\( \)\(B'_i = A'_i + R_i \times (V \times W)\)$
Aoki’s arrival and departure times can also be scaled by \(V \times W\) and computed as integers in the same manner.
Algorithm
We list the timings when speeds change (events) in chronological order and simulate the relative positions of the two runners for each interval between events.
1. Listing and Sorting Events
We generate the following events for Takahashi and Aoki: * Takahashi’s events: * Time \(0\): Depart at speed \(V\) * Arrival time at each water station \(i\) (\(1 \le i < N\)): Speed changes to \(0\) (stop) * Departure time from each water station \(i\) (\(1 \le i < N\)): Speed changes to \(V\) (resume) * Arrival time at the goal \(N\): Speed changes to \(0\) (finish) * Aoki’s events: * Similarly, generate events where speed is \(W\) at time \(0\), speed becomes \(0\) upon arriving at each water station, speed becomes \(W\) upon departing, and speed becomes \(0\) at the goal.
We collect all these events into a single array and sort them in ascending order of time.
2. Merging Events at the Same Time
Multiple events (such as arrival and departure) may occur at the same time, for example, when the stopping time is \(R_i = 0\). We group these as processing at the same time and determine the “final speed” at that moment.
3. Updating Relative Positions for Each Interval
Let the times of adjacent events be \(t_{prev}\) and \(t_{curr}\). Within this time interval, the speeds of both runners are constant.
- Calculate Positions After Movement: Compute the current position by adding the current speed \(\times (t_{curr} - t_{prev})\) to the position at the previous event.
- Determine Sign Change (Overtaking):
Compare the difference in positions at the start of the interval, \(d_{start}\), with the difference at the end, \(d_{end}\).
Maintain a variable
current_signrepresenting the current relative order (\(+1\) if Takahashi is ahead, \(-1\) if Aoki is ahead), and update it as follows:- If both \(d_{start}\) and \(d_{end}\) are non-zero:
- If they have the same sign, there is no change.
- If they have different signs (e.g., \(+ \rightarrow -\)), they crossed in the middle of the interval. We set
current_signto the starting sign, then change it to the ending sign, incrementing the answer each time the “sign changes”.
- If either one is \(0\):
- Compare the non-zero sign (the direction in which the relative order is newly established) with
current_sign, and increment the answer if it has changed.
- Compare the non-zero sign (the direction in which the relative order is newly established) with
- If both \(d_{start}\) and \(d_{end}\) are non-zero:
Complexity
Time Complexity: \(O(N \log N)\)
- Calculating the prefix sums takes \(O(N)\) time.
- The total number of events for both Takahashi and Aoki is \(O(N)\).
- Sorting these events takes \(O(N \log N)\) time.
- The simulation after sorting only requires scanning the events from left to right, which takes \(O(N)\) time.
- Overall, the time complexity is \(O(N \log N)\), which easily runs within the time limit.
Space Complexity: \(O(N)\)
- The sizes of the prefix sum array and the array storing the events are \(O(N)\).
Implementation Points
Handling of Scaled Speed: Since the time axis is scaled by \(V \times W\), we need to scale up the movement speeds while running to \(V \times (V \times W)\) and \(W \times (V \times W)\) respectively when calculating positions. In the code, the position is updated by directly multiplying the scaled time difference by the scaled speed as
speed_F * (curr_t - prev_t).Initialization of
current_sign: At the start (time \(0\)), both are at the same position, so there is no relative order. Therefore, the implementation is designed so thatcurrent_signis initialized for the first time at the moment one of them goes ahead (the first moment where \(d \neq 0\)). This prevents mistakenly counting “one going ahead immediately after departure” as an overtake.Source Code
import sys
def solve():
# Read all inputs from standard input
input_data = sys.stdin.read().split()
if not input_data:
return
N = int(input_data[0])
V = int(input_data[1])
W = int(input_data[2])
R = [int(x) for x in input_data[3:3+N]]
S = [int(x) for x in input_data[3+N:3+2*N]]
# Prefix sums of stopping times to quickly calculate arrival times
pref_R = [0] * (N + 1)
for i in range(N):
pref_R[i+1] = pref_R[i] + R[i]
pref_S = [0] * (N + 1)
for i in range(N):
pref_S[i+1] = pref_S[i] + S[i]
VW = V * W
# We will scale time and position by V * W to keep all calculations in integer arithmetic.
# Event format: (time, person, speed)
# person: 0 for Takahashi (F), 1 for Aoki (G)
events = []
# Takahashi's events
events.append((0, 0, V))
for i in range(1, N):
A_prime = i * W + VW * pref_R[i-1]
B_prime = A_prime + R[i-1] * VW
events.append((A_prime, 0, 0))
events.append((B_prime, 0, V))
# Goal event
A_N_prime = N * W + VW * pref_R[N-1]
events.append((A_N_prime, 0, 0))
# Aoki's events
events.append((0, 1, W))
for i in range(1, N):
C_prime = i * V + VW * pref_S[i-1]
D_prime = C_prime + S[i-1] * VW
events.append((C_prime, 1, 0))
events.append((D_prime, 1, W))
# Goal event
C_N_prime = N * V + VW * pref_S[N-1]
events.append((C_N_prime, 1, 0))
# Sort events chronologically
events.sort()
pos_F = 0
pos_G = 0
speed_F = 0
speed_G = 0
current_sign = None
ans = 0
prev_t = 0
n_events = len(events)
i = 0
while i < n_events:
curr_t = events[i][0]
# Merge events occurring at the exact same time
up_F = None
up_G = None
while i < n_events and events[i][0] == curr_t:
_, person, speed = events[i]
if person == 0:
if up_F is None or speed > up_F:
up_F = speed
else:
if up_G is None or speed > up_G:
up_G = speed
i += 1
if curr_t > 0:
next_pos_F = pos_F + speed_F * (curr_t - prev_t)
next_pos_G = pos_G + speed_G * (curr_t - prev_t)
d_start = pos_F - pos_G
d_end = next_pos_F - next_pos_G
diff_speed = speed_F - speed_G
if diff_speed == 0:
if d_start != 0:
S = 1 if d_start > 0 else -1
if current_sign is None:
current_sign = S
elif current_sign != S:
ans += 1
current_sign = S
else:
if d_start != 0 and d_end != 0:
is_pos_start = d_start > 0
is_pos_end = d_end > 0
if is_pos_start == is_pos_end:
S = 1 if is_pos_start else -1
if current_sign is None:
current_sign = S
elif current_sign != S:
ans += 1
current_sign = S
else:
S1 = 1 if is_pos_start else -1
S2 = -S1
if current_sign is None:
current_sign = S1
elif current_sign != S1:
ans += 1
current_sign = S1
if current_sign is None:
current_sign = S2
elif current_sign != S2:
ans += 1
current_sign = S2
elif d_start == 0 and d_end != 0:
S = 1 if d_end > 0 else -1
if current_sign is None:
current_sign = S
elif current_sign != S:
ans += 1
current_sign = S
elif d_start != 0 and d_end == 0:
S = 1 if d_start > 0 else -1
if current_sign is None:
current_sign = S
elif current_sign != S:
ans += 1
current_sign = S
pos_F = next_pos_F
pos_G = next_pos_G
if up_F is not None:
speed_F = up_F
if up_G is not None:
speed_G = up_G
prev_t = curr_t
print(ans)
if __name__ == '__main__':
solve()
This editorial was generated by gemini-3.5-flash-high.