問題概要
駅Aと駅Bを往復する電車がある
- まず駅AをスタートしてX秒かけて駅Bにくる
- 駅BでY秒待機する
- 駅BをスタートしてX秒かけて駅Aにくる
- 駅AでY秒待機する
以下繰り返し
高橋君は寝ている状態と起きている状態を繰り返す
以下繰り返し
駅Bで待機しているかつ高橋君が起きている時刻の中で最小のものを答えよ
解法
電車の周期2(X+Y)=Cとおくと
Cn + X \le t \lt Cn + X + Yのとき、駅Bに止まる
つまり駅Bで止まる時刻tについて
X \le t \pmod{C} \lt X + Yが成り立つ
高橋君の周期P+Q=Dとおくと
Dn + P \le t \le Dn + P + Qのとき、起きている
つまり起きている時刻tについて
P \le t \pmod{D} \lt P + Qが成り立つ
この問題ではY, Qの制約が小さいので、
X \le a \lt X + Yを満たす整数a、
P \le b \lt P + Qを満たす整数b
を全て試すことができる
このとき
t \equiv a \pmod{C} \\
t \equiv b \pmod{D}
を満たすようなtが答えであり、これは中国剰余定理で答えを求めることができる
すべてのa, bを試してそのminをとればいい
ひとつも満たすものが存在しない場合はinfinityを出力する
提出コード
https://atcoder.jp/contests/abc193/submissions/20572549
Discussion