Official
E - 直線コースの追い越し / Overtaking on a Straight Course Editorial
by
E - 直線コースの追い越し / Overtaking on a Straight Course Editorial
by
sounansya
Editorial for printing
\(2\) 人が各給水所に到着した時刻と出発した時刻をそれぞれ計算していきます。これは \(VW\) 倍すると ( 128bit 以上の整数型が必要になりますが) 整数の範囲で計算することができます。
高橋君・青木君の給水所 \(i\) への到着時刻をそれぞれ \(A_i,B_i\) とし、出発時刻をそれぞれ \(C_i,D_i\) とします。すると、求める答えは \(A_1-B_1,C_1-D_1,A_2-B_2,C_2-D_2,\ldots,A_N-B_N\) の (\(0\) を無視した) 符号の変化した回数と一致します。
これは愚直に計算して \(0\) を消して符号が切り替わった回数を求めれば良いです。
import sys
input = sys.stdin.buffer.readline
n, v, w = map(int, input().split())
r = list(map(int, input().split()))
s = list(map(int, input().split()))
c = d = 0
diff = []
for i in range(n):
a = c + w
b = d + v
diff.append(a - b)
if i < n - 1:
c = a + r[i] * v * w
d = b + s[i] * v * w
diff.append(c - d)
s = [1 if x > 0 else -1 for x in diff if x != 0]
print(sum(s[i - 1] != s[i] for i in range(1, len(s))))
posted:
last update:
