概要

この問題は、周期的に錠がかけられる通路において、特定の時刻に高橋君が体力の範囲内で移動できる部屋の範囲を求める問題です。扉の重さ（錠の数）の累積和が単調増加であることを利用し、二分探索を用いて到達可能な左右の限界を特定します。

考察

1. 扉の重さと累積和

時刻 \(T_j\) を固定すると、各扉 \(x\) の重さ（錠の数）が決まります。 部屋 \(S_j\) から部屋 \(c\) へ移動する際に通過する扉の重さの合計は、扉の番号の区間における重さの総和です。

ここで、扉 \(1\) から扉 \(x\) までの重さの総和を \(D(x)\) と定義します。 - 部屋 \(S_j\) から右側の部屋 \(c\) (\(c > S_j\)) へ移動する場合、通過する扉は \(S_j+1, \dots, c\) なので、重さの合計は \(D(c) - D(S_j)\) となります。 - 部屋 \(S_j\) から左側の部屋 \(c\) (\(c < S_j\)) へ移動する場合、通過する扉は \(c+1, \dots, S_j\) なので、重さの合計は \(D(S_j) - D(c)\) となります。

2. \(D(x)\) の高速な計算

警備パターン \(i\) によって扉 \(x\) に錠がかけられる条件は \(x \equiv (R_i + V_i \cdot T_j) \pmod{A_i}\) です。 \(R'_i = (R_i + V_i \cdot T_j) \pmod{A_i}\) とおくと、パターン \(i\) が錠をかける扉の番号は \(R'_i, R'_i + A_i, R'_i + 2A_i, \dots\) となります。 （ただし、扉の番号は \(1\) 以上なので、\(R'_i = 0\) の場合は \(A_i, 2A_i, \dots\) となります）

このとき、区間 \([1, x]\) に含まれるパターン \(i\) の錠の数は、最初の錠の位置を \(f_i\) とすると： - \(x < f_i\) のとき： \(0\) - \(x \geq f_i\) のとき： \(\lfloor (x - f_i) / A_i \rfloor + 1\) と計算できます。これを全 \(N\) パターンについて合計することで \(D(x)\) を \(O(N)\) で求められます。

3. 二分探索による範囲特定

移動距離が長くなるほど通過する扉の重さの合計は増える（単調増加）ため、二分探索が使えます。 - 右側にどこまで行けるか： \(D(mid) - D(S_j) \leq P_j\) を満たす最大の \(mid \in [S_j, L-1]\) を探す。 - 左側にどこまで行けるか： \(D(S_j) - D(mid) \leq P_j\) を満たす最小の \(mid \in [0, S_j]\) を探す。

アルゴリズム

1. 各クエリ \((T_j, S_j, P_j)\) について以下を行う。
2. 前処理: 各警備パターン \(i\) について、時刻 \(T_j\) における最小の錠の番号 \(f_i\) を計算しておく。
3. 右方向への二分探索:
   • low = Sj, high = L - 1 として、D(mid) - D(Sj) <= Pj を満たす最大の mid を ansR とする。
4. 左方向への二分探索:
   • low = 0, high = Sj として、D(Sj) - D(mid) <= Pj を満たす最小の mid を ansL とする。
5. 回答: 到達可能な部屋の個数は ansR - ansL + 1 である。

計算量

• 時間計算量: \(O(NQ \log L)\)
  • 各クエリに対して \(O(N)\) の前処理と、\(O(N \log L)\) の二分探索（\(D(x)\) の計算に \(O(N)\) かかるため）を行います。
  • 制約 \(N \times Q \le 3 \times 10^5\) により、この計算量で実行時間制限に間に合います。
• 空間計算量: \(O(N)\)
  • 警備パターンの情報を保持するメモリが必要です。

実装のポイント

• \(R'_i = 0\) の扱い: 扉の番号は \(1\) から始まるため、余りが \(0\) の場合の最初の扉は \(0\) ではなく \(A_i\) になります。

• オーバーフロー: 体力 \(P_j\) や重さの総和 \(D(x)\) は非常に大きな値（最大 \(10^{14}\) 程度）になる可能性があるため、long long 型を使用する必要があります。

• 高速化: \(N \times Q\) が大きいため、C++の場合は cin.tie(nullptr); ios::sync_with_stdio(false); を使用して入出力を高速化することが推奨されます。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

/**
 * get_D calculates the prefix sum of door weights from door 1 up to door x.
 * A door x (1 <= x <= L-1) has a lock from security pattern i if
 * x ≡ (R_i + V_i * T_j) (mod A_i).
 * 
 * Let R'_i = (R_i + V_i * T_j) mod A_i.
 * The smallest k >= 1 such that k ≡ R'_i (mod A_i) is:
 * - A_i if R'_i == 0
 * - R'_i if R'_i > 0
 * Let this smallest k be first_k[i].
 * The number of such k in [1, x] is:
 * - 0 if x < first_k[i]
 * - floor((x - first_k[i]) / A_i) + 1 if x >= first_k[i]
 */
long long get_D(long long x, int N, const vector<long long>& first_k, const vector<long long>& A) {
    if (x <= 0) return 0;
    long long total = 0;
    for (int i = 0; i < N; ++i) {
        if (x >= first_k[i]) {
            total += (x - first_k[i]) / A[i] + 1;
        }
    }
    return total;
}

struct Pattern {
    long long A, R, V;
};

int main() {
    // Faster I/O for competitive programming
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long L;
    int Q;
    if (!(cin >> N >> L >> Q)) return 0;

    // Store security patterns
    vector<Pattern> patterns(N);
    for (int i = 0; i < N; ++i) {
        cin >> patterns[i].A >> patterns[i].R >> patterns[i].V;
    }

    // Vectors to store precomputed values for each query
    vector<long long> first_k(N);
    vector<long long> A_vals(N);

    // Process each query
    for (int j = 0; j < Q; ++j) {
        long long Tj, Sj, Pj;
        cin >> Tj >> Sj >> Pj;

        // Precompute the smallest door index for each pattern at time Tj
        for (int i = 0; i < N; ++i) {
            long long Ri_prime = (patterns[i].R + patterns[i].V * Tj) % patterns[i].A;
            first_k[i] = (Ri_prime == 0 ? patterns[i].A : Ri_prime);
            A_vals[i] = patterns[i].A;
        }

        // Prefix sum of door weights up to room Sj
        long long D_Sj = get_D(Sj, N, first_k, A_vals);

        // Binary search for the rightmost reachable room ansR in [Sj, L-1]
        // Sum of weights of doors between Sj and mid (mid > Sj) is D(mid) - D(Sj)
        long long lowR = Sj, highR = L - 1;
        long long ansR = Sj;
        while (lowR <= highR) {
            long long mid = lowR + (highR - lowR) / 2;
            if (get_D(mid, N, first_k, A_vals) - D_Sj <= Pj) {
                ansR = mid;
                lowR = mid + 1;
            } else {
                highR = mid - 1;
            }
        }

        // Binary search for the leftmost reachable room ansL in [0, Sj]
        // Sum of weights of doors between mid and Sj (mid < Sj) is D(Sj) - D(mid)
        long long lowL = 0, highL = Sj;
        long long ansL = Sj;
        while (lowL <= highL) {
            long long mid = lowL + (highL - lowL) / 2;
            if (D_Sj - get_D(mid, N, first_k, A_vals) <= Pj) {
                ansL = mid;
                highL = mid - 1;
            } else {
                lowL = mid + 1;
            }
        }

        // Output the number of reachable rooms in the range [ansL, ansR]
        cout << ansR - ansL + 1 << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。