E - 直線コースの追い越し / Overtaking on a Straight Course 解説 by admin
gemini-3.5-flash-high概要
この問題は、一直線のコース上を異なる速さで走る高橋君と青木君が、給水所で立ち止まりながらゴールを目指す中で、お互いを「追い越した」回数の合計を求める問題です。
二人の位置の差の符号（どちらが前にいるか）が変化する瞬間を、浮動小数点数の誤差を排除した整数演算のみのイベントソート（シミュレーション）によって正確に数え上げます。
考察
1. 「追い越し」の定義と判定
ある時刻 \(t\) における高橋君の位置を \(f(t)\)、青木君の位置を \(g(t)\) とします。二人の位置の差を \(D(t) = f(t) - g(t)\) と定義すると、追い越しとは \(D(t)\) の符号が正から負、あるいは負から正に変化することに相当します。
\(D(t) = 0\)（二人が同じ位置にいる）の状態が一定時間続いた後に前後関係が入れ替わる場合も追い越し \(1\) 回と数えますが、入れ替わらずに元の前後関係に戻る場合は追い越しとは数えません。
2. 浮動小数点数による誤差の回避（最重要）
高橋君がスタートしてから給水所 \(i\) に到着するまでの時間は、走った距離 \(i\) を速さ \(V\) で割った値に、それまでの給水所での停止時間を加えたものです。
素直に計算すると \(\frac{i}{V}\) という分数が登場し、これをプログラム上で float や double などの実数型で扱うと、丸め誤差によって正しい判定ができなくなります（特に \(N \le 5 \times 10^5\) と制約が大きいため、微小な誤差が致命的になります）。
そこで、時間と位置のスケールを \(V \times W\) 倍にします。
- 高橋君の本来の速度は \(V\)、青木君の本来の速度は \(W\) です。
- 時間を \(V \times W\) 倍すると、それぞれの「走っているときの速度」は以下のようになります：
- 高橋君の速度: \(V \times (V \times W) \rightarrow\) 単位時間あたりに進む距離が \(V\) であったものが、時間を \(V \times W\) 倍した世界では、給水所間の距離 \(1\) を進むのに必要な（スケールされた）時間は \(W\) となります。
- 青木君の速度: \(W \times (V \times W) \rightarrow\) 同様に、給水所間の距離 \(1\) を進むのに必要な時間は \(V\) となります。
- これにより、すべてのイベントが発生する時刻を整数で表すことができます。
具体的な時刻の変換
高橋君が給水所 \(i\) に到着する元の時刻を \(A_i\)、出発する元の時刻を \(B_i\) とします（停止時間の累積和を \(P_R\) とします）。 $\(A_i = \frac{i}{V} + P_R[i-1]\)\( \)\(B_i = A_i + R_i\)$
これを \(V \times W\) 倍した時刻 \(A'_i, B'_i\) は以下のようになり、すべて整数で計算可能です。 $\(A'_i = i \times W + (V \times W) \times P_R[i-1]\)\( \)\(B'_i = A'_i + R_i \times (V \times W)\)$
青木君の到着・出発時刻についても、同様に \(V \times W\) 倍して整数として求められます。
アルゴリズム
速度が変化するタイミング（イベント）を時系列順に並べ、イベント間の区間ごとに二人の位置関係をシミュレーションします。
1. イベントの列挙とソート
高橋君と青木君のそれぞれについて、以下のイベントを生成します。 * 高橋君のイベント: * 時刻 \(0\): 速度 \(V\) で出発 * 各給水所 \(i\) (\(1 \le i < N\)) への到着時刻: 速度 \(0\) に変化（停止） * 各給水所 \(i\) (\(1 \le i < N\)) からの出発時刻: 速度 \(V\) に変化（再開） * ゴール \(N\) への到着時刻: 速度 \(0\) に変化（終了） * 青木君のイベント: * 同様に、時刻 \(0\) に速度 \(W\)、各給水所への到着で速度 \(0\)、出発で速度 \(W\)、ゴールで速度 \(0\) となるイベントを生成
これらのイベントをすべて一つの配列にまとめ、時刻の昇順にソートします。
2. 同一時刻のイベントの統合
停止時間 \(R_i = 0\) の場合など、同じ時刻に複数のイベント（到着と出発）が発生することがあります。これらは同一時刻の処理としてまとめ、その時刻における「最終的な速度」を確定させます。
3. 区間ごとの位置関係の更新
隣り合うイベントの時刻を \(t_{prev}\) から \(t_{curr}\) とします。この時間内では二人の速度は一定です。
- 移動後の位置の計算: 前のイベント時点の位置から、現在の速度 \(\times (t_{curr} - t_{prev})\) を足して、現在の位置を求めます。
- 符号の変化（追い越し）の判定:
区間の開始時の位置の差 \(d_{start}\) と、終了時の位置の差 \(d_{end}\) を比較します。
現在の前後関係を表す変数
current_sign（高橋君が前なら \(+1\)、青木君が前なら \(-1\)）を持ち、以下のように更新します：- \(d_{start}\) と \(d_{end}\) がともに \(0\) でない場合：
- 符号が同じなら変化なし。
- 符号が異なる（例：\(+ \rightarrow -\)）なら、区間の途中で交差しています。
current_signを開始時の符号にした後、終了時の符号へと変化させ、その都度「符号が変わった」として答えをインクリメントします。
- どちらか一方が \(0\) の場合：
- \(0\) でない側の符号（新しく前後関係が確定した方向）を
current_signと比較し、変化していれば答えをインクリメントします。
- \(0\) でない側の符号（新しく前後関係が確定した方向）を
- \(d_{start}\) と \(d_{end}\) がともに \(0\) でない場合：
計算量
時間計算量: \(O(N \log N)\)
- 累積和の計算に \(O(N)\) 時間かかります。
- イベントの総数は高橋君と青木君を合わせて \(O(N)\) 個です。
- これらのイベントをソートするのに \(O(N \log N)\) 時間かかります。
- ソート後のシミュレーションは、イベントを前から順に走査するだけなので \(O(N)\) 時間です。
- 全体として \(O(N \log N)\) となり、制限時間内に余裕で間に合います。
空間計算量: \(O(N)\)
- 累積和配列、およびイベントを格納する配列のサイズは \(O(N)\) です。
実装のポイント
スケールされた速度の扱い: 時間軸を \(V \times W\) 倍したため、走っているときの移動速度もそれぞれ \(V \times (V \times W)\) および \(W \times (V \times W)\) にスケールアップして位置を計算する必要があります。コード内では
speed_F * (curr_t - prev_t)として、スケールされた時間差とスケールされた速度をそのまま掛け合わせて位置を更新しています。current_signの初期化: スタート時点（時刻 \(0\)）では二人は同じ位置にあり、前後関係が存在しません。そのため、最初にどちらかが前に出た瞬間（最初の \(d \neq 0\) となる瞬間）にcurrent_signが初めて初期化されるように実装されています。これにより「出発直後に一方が前に出ること」を誤って追い越しとしてカウントするのを防いでいます。ソースコード
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()
この解説は gemini-3.5-flash-high によって生成されました。
投稿日時:
最終更新: