公式
E - Oversleeping 解説 by tatyam
電車と高橋くんの状態が変化するのが整数時刻のみなので、それぞれの整数時刻に高橋くんが街 \(B\) で降りられるかどうか判定すれば十分です。
すると、以下の問題を解けば良いです。
- \(X ≤ t \bmod (2X+2Y) < X + Y\)
- \(P ≤ t \bmod (P + Q) < P + Q\)
となる最小の非負整数 \(t\) はいくつか?
ここで、\(Y, Q ≤ 500\) と、電車が街 \(B\) で停車している時間と高橋くんが起きている時間が短いことに注目し、\(t \bmod (2X+2Y)\) と \(t \bmod (P + Q)\) の値を全探索します。
すると、以下の問題を解けば良いです。
整数 \(t_1(X ≤ t_1 < X + Y),\ t_2(P ≤ t_2 < P + Q)\) が与えられる。
- \(t = t_1 \pmod{2X+2Y}\)
- \(t = t_2 \pmod{P + Q}\)
となる最小の非負整数 \(t\) はいくつか?
これは、拡張ユークリッドの互除法により \(O(\log(X+Y+P+Q))\) で求めることができるので、全体で \(O(YQ\log(X+Y+P+Q))\) の計算量でこの問題を解くことができます。
実装には AC Library の crt を利用できます。
回答例 (C++)
#include <bits/stdc++.h>
#include <atcoder/math>
using namespace std;
using ll = int64_t;
const ll INF = numeric_limits<ll>::max() / 4;
void solve(){
ll X, Y, P, Q;
cin >> X >> Y >> P >> Q;
ll ans = INF;
for(ll t1 = X; t1 < X + Y; t1++) for(ll t2 = P; t2 < P + Q; t2++){
auto [t, lcm] = atcoder::crt({t1, t2}, {(X + Y) * 2, P + Q});
if(lcm == 0) continue;
if(ans > t) ans = t;
}
if(ans == INF) puts("infinity");
else cout << ans << endl;
}
int main(){
ll T;
cin >> T;
while(T--) solve();
}
BONUS : \(O(Y+Q+\log(X+Y+P+Q))\) で解いてみましょう!
投稿日時:
最終更新: