No.61 リベリオン

No.61 リベリオン - yukicoder

• 鏡面反転のアイデアは思いついたけど、反転後の Mx,My の座標をどう求めればいいかわからなかった。
• そっちの解法は Extra で学ぶとして、この問題の制約ではシミュレーションで十分だった。
• 格子点ごとの移動をさせるために最大公約数を計算するのと、一秒間の移動で反転が複数回行われるケースに対応するのがポイントだと思う。

class Rebellion {
public:
    void solve(void) {
            int Q;
            cin>>Q;

            // H,W の制約が小さいので 1 クエリにたいして O(16^2*4) <= 1024 程度
            // 同じ (x,y) 座標で方向が同じ場合ループになるので D は最大 1050 程度まで調べれば良い
            // シミュレーションで十分間に合う
            REP(q,Q)
            {
                int W,H,Mx,My,Hx,Hy;
                ll  D,Vx,Vy;
                cin>>W>>H>>D>>Mx>>My>>Hx>>Hy>>Vx>>Vy;

                // 1 秒ごとの移動で格子点上に移動させるため Vx,Vy は互いに素になるようにしておく
                ll k = gcd(abs(Vx),abs(Vy));
                Vx /= k;
                Vy /= k;
                D = min(1050LL, D*k);

                int x,y;
                x = Hx;
                y = Hy;
                bool hit = false;
                for (int d = 1; d <= D; ++d)
                {
                    // 1 秒経過ごとに移動させる
                    x += Vx;
                    y += Vy;

                    //  W = 3, H = 10, Vx = 15, Vy = 1
                    //  みたいなケースでは反転が複数回おこなわれるので対応
                    while (true)
                    {
                        if (x < 0) { Vx *= -1; x = -x;    continue; }
                        if (x > W) { Vx *= -1; x = 2*W-x; continue; }
                        if (y < 0) { Vy *= -1; y = -y;    continue; }
                        if (y > H) { Vy *= -1; y = 2*H-y; continue; }
                        break;
                    }

                    if (x == Mx && y == My)
                    {
                        hit = true;
                        break;
                    }
                }
                if (hit)
                    cout<<"Hit"<<endl;
                else
                    cout<<"Miss"<<endl;
            }
    }
};