【Codeforces】Codeforces Round 927 (Div. 3) G. Moving Platforms

解法

現在時刻を $t$ とすると、ダイクストラ法で各遷移において $L _{i} + S _{i} x ≡ L _{j} + S _{j} x \pmod H$ となる最小の $x > t$ を求めることができれば良いので線形合同式が解ければ良い。

しかしこれを解くのは意外と難しく、法が素数ではないときに逆元がないが $x$ が解を持つという場合がある。（例： $9x \equiv 3 \pmod {15}$ に対し $x \equiv 2 \pmod 5$ ）

なので tourist 氏や maspy 氏のコードを参考にライブラリを作成した。

結局のところ $ax + by = c$ が解ければ良いのだが、解 $(x, y)$ が求められたときに $x$ の周期が $b$ ではなく $b / gcd(a, b)$ であるという点に注意する。

#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "math/linear_diophantine.hpp"

using namespace std;

void solve() {
    I64(N, M, H);
    VEC(i64, L, N);
    VEC(i64, S, N);
    auto g = read_graph<int>(N, M);

    vector<i64> dp(N, INF<i64>);
    pqueg<pair<i64, int>> que;
    dp[0] = -1;
    que.emplace(-1, 0);

    while (!que.empty()) {
        auto [t, i] = que.top();
        que.pop();
        if (t != dp[i]) continue;
        FORE(e, g[i]) {
            int j = e.to;
            // L[i] + S[i] * x ≡ L[j] + S[j] * x (mod H) となる x を求める
            // (S[i] - S[j]) * x ≡ L[j] - L[i] (mod H)
            auto [x, mod] = linear_congruence(S[i] - S[j], L[j] - L[i], H);
            if (mod == -1) continue;
            i64 nt = (t + 1);
            if (nt % mod <= x) {
                nt = nt / mod * mod + x;
            } else {
                nt = ceil(nt, mod) * mod + x;
            }
            if (chmin(dp[e.to], nt)) {
                que.emplace(dp[e.to], e.to);
            }
        }
    }
    i64 ans = dp[N - 1] + 1;
    if (ans >= INF<i64> / 2) ans = -1;
    print(ans);
    return;
}

int main() {
    INT(T);
    REP(T) solve();
    return 0;
}

感想

線形合同式を理解し直すことができて良かった。