yukicoder No.62 リベリオン(Extra)

解法の概要

中国余剰定理を用いた多倍長整数を必要としない解法です。

解法

密室の幅を$W$、奥行きを$H$、時間を$D$秒間止め、まみの座標を$ (M_x, M_y) $、ほむらの座標を$(H_x, H_y)$ 、弾丸の一秒間に進む速度を$ (V_x,V_y) $とします。
まず、$(V_x,V_y)$について最大公約数をとります。例えば、1秒後に$(2, 4)$という速度であった場合、$(1, 2)$は0.5秒後に到達することになります。整数で扱うには都合が悪いため、速度を$(V_x/{\rm gcd}(V_x,V_y), V_y/{\rm gcd}(V_x,V_y))$とすることで整数座標には整数時間にしか訪れないという変換ができます。当然速度が${\rm gcd}(V_x,V_y)$分の1となるため、時間$D$を$D*{\rm gcd}(V_x,V_y)$としてあげます。
以下、$V_x$,$V_y$が登場した際は $V_x/{\rm gcd}(V_x, V_y)$、$V_y/{\rm gcd}(V_x, V_y)$を指すものとします。

この密室を無限に広い空間に変換します。これは、$(2W, 2H)$の空間が周期的に現れていると解釈することで可能です。($(W, H)$を横断する度に鏡のように反転しているというイメージです。)
$(2W, 2H)$の中に$(W, H)$の領域が4つあって、それらが鏡のような対称性をもっていると考えると、まみは${\rm mod}(2W, 2H)$として、$(M_x, M_y)$、$(-M_x, M_y)$、$(M_x, -M_y)$、$(-M_x, -M_y)$の4点にいることが分かるかと思います。

まみが$(M_x, M_y)$にいる場合を考えます。時間を$t$とすると、弾丸の座標とまみの座標が一致する条件は $$ M_x = V_x t + H_x \,\,({\rm mod}\,2W) $$ $$ M_y = V_yt + H_y \,\,({\rm mod}\,2H) $$ となります。時刻$t$について変形すると、 $$ t = \frac{M_x - H_x}{V_x}\,\,({\rm mod}\,2W) = \frac{M_y - H_y}{V_y}\,\,({\rm mod}\,2H) $$ となります。この際、$V_x$と$2W$、$V_y$と$2H$は互いに素にしておく必要があります(互いに素でないと逆元を求めることができない)ので、それぞれ、${\rm gcd}(V_x, 2W)$と${\rm gcd}(V_y, 2H)$をとっておき、それぞれ
$$ V_x \leftarrow \frac{V_x}{{\rm gcd}(V_x, 2W)}　m_x = \frac{M_x - H_x}{{\rm gcd}(V_x, 2W)}　D_x = \frac{2W }{ {\rm gcd}(V_x, 2W)} $$ $$ V_y \leftarrow \frac{V_y}{{\rm gcd}(V_y, 2H)}　m_y = \frac{M_y - H_y}{{\rm gcd}(V_y, 2H)}　D_y = \frac{2W}{ {\rm gcd}(V_y, 2H)} $$ としておきます。$M_x - H_x$が${\rm gcd}(V_x, 2W)$で割り切れない場合や$M_y - H_y$が${\rm gcd}(V_y, 2H)$で割り切れない場合は逆元が存在しないため解が存在しないことになります。
これらをもとの式に当てはめると、 $$ t = \frac{m_x}{V_x}\,\,({\rm mod}\,D_x) = \frac{m_y}{V_y}\,\,({\rm mod}\,D_y) $$ となりますので、この$t$ を中国余剰定理で求めることにより、$t \leq D \times {\rm gcd}(V_x, V_y) $となっているかを判定すればこの問題を解くことができます。他のまみの座標$(-M_x, M_y)$、$(M_x, -M_y)$、$(-M_x, -M_y)$についても同様にして解くことができます。

実装例

実装にはAtCoder Libraryのinv_modとcrtを用いています。

#include<atcoder/all>
using namespace std;
using namespace atcoder;

int main(){
    int t;
    cin >> t;
    while(t--){
        long long W, H, D, Mx, My, Hx, Hy, Vx, Vy, g, gx, gy, Dx, Dy, mx, my;
        cin >> W >> H >> D >> Mx >> My >> Hx >> Hy >> Vx >> Vy;
        g = gcd(Vx, Vy);
        Vx /= g, Vy /= g, D *= g;
        gx = gcd(Vx, 2 * W), gy = gcd(Vy, 2 * H);
        Vx /= gx, Dx = 2 * W / gx;
        Vy /= gy, Dy = 2 * H / gy;
        bool ans = false;
        for(int i = 0; i < 4; i++){
            mx = (i & 1? 1: -1) * Mx - Hx;
            my = (i & 2? 1: -1) * My - Hy;
            if(mx % gx != 0 || my % gy != 0)continue;
            mx /= gx, my /= gy;
            mx *= inv_mod(Vx, Dx);
            my *= inv_mod(Vy, Dy);
            auto T = crt({mx, my}, {Dx, Dy});
            if(T.second == 0)continue;
            if(T.first <= D)ans = true;
        }
        cout << (ans ? "Hit" : "Miss") << '\n';
    }
}