📑

ABC193 E - Oversleeping

2021/02/28に公開約700字

問題概要

駅Aと駅Bを往復する電車がある

  • まず駅AをスタートしてX秒かけて駅Bにくる
  • 駅BでY秒待機する
  • 駅BをスタートしてX秒かけて駅Aにくる
  • 駅AでY秒待機する

以下繰り返し

高橋君は寝ている状態と起きている状態を繰り返す

  • P秒寝る
  • Q秒起きる

以下繰り返し

駅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

ログインするとコメントできます