【AtCoder】ABC 421 D - RLE Moving | 緑コーダーが解くAtCoder

配点: 425 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1321 / NoviSteps: ???

問題概要
制約
考察
実装例
コメント

問題概要

無限に広いグリッドがあり、マス $(0,0)$ から下に $r$ マス、右に $c$ マス移動した位置にあるマスをマス $(r,c)$ と呼ぶ。

最初、高橋君はマス $(R_t,C_t)$ に、青木君はマス $(R_a,C_a)$ にいる。二人はそれぞれU, D, L, Rからなる長さ $N$ の文字列 $S,T$ に従って $N$ 回移動を行う。各 $i$ について、高橋君と青木君の $i$ 回目の移動は同時に行われる。

$N$ 回の移動の中で、移動直後に高橋君と青木君が同じマスにいた回数を求めよ。ただし、 $N$ は非常に大きいため、 $S,T$ はランレングス圧縮された形で与えられる。

制約

$-10^9 \leq R_t,C_t,R_a,C_a \leq 10^9$
$1\leq N \leq 10^{14}$
与えられる数値は全て整数。

考察

$N$ が大きすぎるので、愚直に二人の動きをシミュレーションするのは不可能。

そこで、二人の動きを一つにまとめてしまおう。つまり、二人の位置の相対座標を管理するのである。

このとき、

高橋君がマス $(R_t, C_t)$ から向こう $A_i$ 回にわたって方向 $(dR_t, dC_t)$ へ移動する。
青木君がマス $(R_a, C_a)$ から向こう $B_j$ 回にわたって方向 $(dR_a, dC_a)$ へ移動する。

というケースは、

二人の相対座標は向こう回にわたって方向へ移動する。ただし、
- $R_{ta} = R_t - R_a, \quad C_{ta} = C_t - C_a$
- $dR_{ta} = dR_t - dR_a, \quad dC_{ta} = dC_t - dC_a$

のように言い換えられる。相対座標の移動方向が一定なのは、それぞれの移動の連続区間の共通部分のみであることに注意しよう。

さて、今考えたいのは、「 $(R_{ta}, C_{ta})$ から方向 $(dR_{ta}, dC_{ta})$ へ $s$ 回移動する間に、相対座標が $(0, 0)$ になることがあるかどうか」である。これを数式で書くと、

$\begin{align*} (R_{ta} + k dR_{ta}, C_{ta} + k dC_{ta}) & = 0 \iff \left\{ \begin{array}{ll} R_{ta} + k dR_{ta} & = 0 \\ C_{ta} + k dC_{ta} & = 0 \end{array} \right. \end{align*}$

を満たすような整数 $k$ が存在すればよいことになる。つまり、以下のような $k$ が存在するたびに、答えに $1$ を加算する。

$\begin{align*} k = -\frac{R_{ta}}{dR_{ta}} = -\frac{C_{ta}}{dC_{ta}}, \: 1 \leq k \leq s, \: k \in \mathbb{Z} \end{align*}$

この条件を (#) とする。

大まかな方針はこれで立ったわけだが、 $k$ の存在条件の式から、考えるべき例外ケースが考えられる。

それは、分母が $0$ のとき。すなわち、 $dR_{ta}, dC_{ta}$ が $0$ となるときである。これについて、考えられる3パターンを順に考えていく。

$dR_{ta} = 0$ かつ $dC_{ta} = 0$ のとき :

これは、 $s$ 回の移動において、相対座標が変わらないことを意味している。したがって、元々 $(R_{ta}, C_{ta}) = (0, 0)$ なら答えに $s$ を加算すればいいし、そうでなければスキップすればよい。

上のケースに当てはまらず、 $dR_{ta} = 0$ のとき :

これは、相対座標が列方向にしか変化しないことを意味している。したがって、元々 $R_{ta} = 0$ であり且つ $-\frac{C_{ta}}{dC_{ta}}$ が条件 (#) を満たすならば、答えに $1$ を加算する。

上のケースに当てはまらず、 $dC_{ta} = 0$ のとき :

これは、相対座標が行方向にしか変化しないことを意味している。したがって、元々 $C_{ta} = 0$ であり且つ $-\frac{R_{ta}}{dR_{ta}}$ が条件 (#) を満たすならば、答えに $1$ を加算する。

ここまで考察できれば、あとは地道に実装していくだけである。~~これがクソだるい...~~

実装例

実装のポイントとして、

U, D, L, Rを2次元ベクトルに変換できるように、前者を key とするmapを用意しておく。
二人それぞれの移動方向の連続部分における残りの回数を保持するために、rest_T, rest_Aを用意する。

を挙げておく。あとは分数のゼロ除算例外と $k$ の整数判定をしっかり行おう。

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    ll Rt, Ct, Ra, Ca;
    cin >> Rt >> Ct >> Ra >> Ca;
    ll N;
    int M, L;
    cin >> N >> M >> L;
    vector<pair<char, ll>> T(M), A(L);
    rep(i, 0, M) cin >> T[i].first >> T[i].second;
    rep(i, 0, L) cin >> A[i].first >> A[i].second;

    map<char, pair<int, int>> dir = {
        {'U', {-1, 0}},
        {'D', {1, 0}},
        {'L', {0, -1}},
        {'R', {0, 1}}};

    ll ans = 0;
    int T_idx = 0, A_idx = 0;
    int rest_T = T[0].second, rest_A = A[0].second;
    while (T_idx < M && A_idx < L)
    {
        ll s = min(rest_T, rest_A);
        ll Rta = Rt - Ra, Cta = Ct - Ca;
        pair<ll, ll> dt = dir[T[T_idx].first], da = dir[A[A_idx].first];
        ll dRta = dt.first - da.first, dCta = dt.second - da.second;

        if (dRta == 0 && dCta == 0)
        {
            if (Rta == 0 && Cta == 0)
                ans += s;
        }
        else
        {
            ll k = -1;
            if (dRta == 0)
            {
                if (Rta == 0 && Cta % dCta == 0)
                    k = -Cta / dCta;
            }
            else if (dCta == 0)
            {
                if (Cta == 0 && Rta % dRta == 0)
                    k = -Rta / dRta;
            }
            else
            {
                if (Rta % dRta == 0 && Cta % dCta == 0)
                {
                    if (-Rta / dRta == -Cta / dCta)
                        k = -Rta / dRta;
                }
            }

            if (1 <= k && k <= s)
                ans++;
        }

        Rt += s * dt.first;
        Ct += s * dt.second;
        Ra += s * da.first;
        Ca += s * da.second;

        rest_T -= s, rest_A -= s;
        if (rest_T == 0)
        {
            T_idx++;
            if (T_idx < M)
                rest_T = T[T_idx].second;
        }
        if (rest_A == 0)
        {
            A_idx++;
            if (A_idx < L)
                rest_A = A[A_idx].second;
        }
    }

    cout << ans << endl;

    return 0;
}