📑

ABC193 E - Oversleeping

2021/02/28に公開

競技プログラミング

tech

問題概要

駅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を出力する

ABC193 E - Oversleeping

問題概要

解法

提出コード

Discussion