ABC193 E Oversleeping - 文学徒が競プロをするブログ

問題文読んでウっとなりかけたけど、単に超丁寧に書いてくれてただけでしたね。ありがとう。

バチャ参加したときは寝不足で頭が回らずとても解ける状況ではなかったので、改めて解き直します。

TwitterでCRTを使うという本質情報を得ていたので自力出来ました。CRTで解けるって聞いてなかったら解けなかったかな...どうだろう。

問題概要

問題文が長くてさすがに面倒なので、リンクだけ貼っておきます。

見てとりあえず何か周期をごにょごにょする問題っぽいことがわかります。

とりあえず条件を式で綺麗に表せないと始まらなさそうなので、式をよーく見ます。

$(2X+2Y)n + X \leq t \lt (2X+2Y)n + X + Y$

かつ

$(P+Q)m + P \leq t \lt (P+Q)(m+1)$

となる $t$ を求めます。

とりあえず、 $(2X+2Y)n + X = (P+Q)m+P$ のときを考えてみます。この数式は「B駅に着いた時間にちょうど高橋君が目を覚ました」ということを意味するので、この数式を満たす解が存在するとき、その解が示す時間に高橋君は電車から降りることが出来ます。

そして、 $X,Y,P,Q$ は定数です。試しに $X = 1, Y = 1, P = 5, Q = 5$ と置いてみます。

すると

$(2X+2Y)n + X = (P+Q)m+P$ は

$4n+1 = 10m+5$

と表すことが出来ます。これは4の倍数+1と10の倍数+5が等しいという等式なので、「4で割って1あまり、10で割って5あまる一番小さな数ってなーんだ？」という問題に言い換えられます。

要は

$t \equiv 1\ (mod\ 4)$

$t \equiv 5\ (mod\ 10)$

と表すことが出来て、これは拡張ユークリッドの互除法なりで解けることで有名です。

問題は与えられた数式が不等式になっていることですが、よく見ると $P, Q \leq 500$ と制約が小さくなっており、2乗を回しても十分間に合うので、普通に全部の区間を試せば良いです。

地味にサンプルの三つめがめっちゃ優しいですね(最大値が ${10}^{18}$ ではギリギリ足りないことを教えてくれている)。ありがとうAtCoder。今まで不親切が続いていたのにどうしたんでしょう？今後もこうあってくれると泣いて喜びます。