概要

固定時刻における各扉の「重さ」（錠の数）を区間で合計する関数を作り、二分探索で左右それぞれに到達可能な最遠の部屋を求める問題です。

考察

扉の重さの構造

時刻 \(T\) を固定すると、警備パターン \(i\) が扉 \(x\) に錠をかける条件は： $\(x \equiv C_i \pmod{A_i} \quad \text{ただし } C_i = (R_i + V_i \cdot T) \bmod A_i\)$

つまり、パターン \(i\) は \(C_i, C_i + A_i, C_i + 2A_i, \ldots\) という等差数列の位置の扉に錠をかけます。

区間の重さの合計

区間 \([lo, hi]\) にある扉の重さの合計は、各パターン \(i\) について「\([lo, hi]\) の中に \(x \equiv C_i \pmod{A_i}\) を満たす \(x\) がいくつあるか」を足し合わせたものです。これは次の式で \(O(N)\) で計算できます：

\[\text{count}_i = \left\lfloor \frac{hi - C_i}{A_i} \right\rfloor - \left\lfloor \frac{lo - 1 - C_i}{A_i} \right\rfloor\]

単調性と二分探索

部屋 \(S\) から右に \(k\) 部屋進むには扉 \(S+1, S+2, \ldots, S+k\) を通ります。\(k\) を増やすと通過する扉が増えるため、重さの合計は単調非減少です。したがって「重さの合計 \(\leq P\)」を満たす最大の \(k\) は二分探索で求められます。左方向も同様です。

計算量が間に合う理由

制約 \(N \times Q \leq 3 \times 10^5\) がポイントです。各クエリで二分探索を2回行い、各ステップで \(O(N)\) の計算をしますが、\(\log L \leq 30\) 程度なので全体で \(O(N \times Q \times \log L) \approx 9 \times 10^6\) となり十分間に合います。

アルゴリズム

1. 各クエリ \((T_j, S_j, P_j)\) に対して：

   • 各パターン \(i\) の \(C_i = (R_i + V_i \cdot T_j) \bmod A_i\) を計算する。
   • 右方向の二分探索: \(\text{total\_weight}(S+1, S+k) \leq P\) を満たす最大の \(k\)（\(0 \leq k \leq L-1-S\)）を求める。
   • 左方向の二分探索: \(\text{total\_weight}(S-k+1, S) \leq P\) を満たす最大の \(k\)（\(0 \leq k \leq S\)）を求める。
   • 答えは \(\text{left\_rooms} + \text{right\_rooms} + 1\)（自分自身の部屋を含む）。

2. total_weight(lo, hi) は上述の式で各パターンの寄与を合計する。

具体例

\(A=3, C=1\) のパターンがあり、区間 \([1, 7]\) の扉を考えると、錠がかかる扉は \(1, 4, 7\) の3つです。 $\(\left\lfloor \frac{7-1}{3} \right\rfloor - \left\lfloor \frac{0-1}{3} \right\rfloor = 2 - (-1) = 3\)$

計算量

• 時間計算量: \(O(N \cdot Q \cdot \log L)\)（制約より \(N \cdot Q \leq 3 \times 10^5\), \(\log L \leq 30\) なので十分高速）
• 空間計算量: \(O(N)\)

実装のポイント

• 負の数の除算: C++の整数除算は0方向に切り捨てるため、数学的な床関数（負の無限大方向への切り捨て）を別途実装する必要があります。コード中の floor_div がそれに当たります。

• オーバーフロー対策: \(V_i \cdot T\) は最大 \(10^9 \times 10^9 = 10^{18}\) になるため long long が必須です。体力 \(P\) も \(10^{14}\) まであります。

• \(k=0\) の場合: 扉を1つも通らない場合（その場で留まる）は常に可能なので、二分探索で mid == 0 のケースを特別に処理しています。

  ソースコード

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

long long floor_div(long long a, long long b) {
    return a / b - (a % b != 0 && (a ^ b) < 0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    long long L;
    cin >> N >> L >> Q;
    
    vector<long long> A(N), R(N), V(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> R[i] >> V[i];
    }
    
    for (int j = 0; j < Q; j++) {
        long long T, S, P;
        cin >> T >> S >> P;
        
        vector<long long> C(N);
        for (int i = 0; i < N; i++) {
            C[i] = (R[i] + V[i] * T) % A[i];
        }
        
        // Compute total weight of doors in [lo, hi]
        auto total_weight = [&](long long lo, long long hi) -> long long {
            if (lo > hi) return 0;
            long long sum = 0;
            for (int i = 0; i < N; i++) {
                sum += floor_div(hi - C[i], A[i]) - floor_div(lo - 1 - C[i], A[i]);
            }
            return sum;
        };
        
        // Binary search right: find max k such that total_weight(S+1, S+k) <= P
        long long right_rooms = 0;
        {
            long long lo = 0, hi = L - 1 - S;
            while (lo <= hi) {
                long long mid = (lo + hi) / 2;
                if (mid == 0 || total_weight(S + 1, S + mid) <= P) {
                    right_rooms = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        
        // Binary search left: find max k such that total_weight(S-k+1, S) <= P
        // Going left from room S by k rooms means passing through doors S, S-1, ..., S-k+1
        long long left_rooms = 0;
        {
            long long lo = 0, hi = S;
            while (lo <= hi) {
                long long mid = (lo + hi) / 2;
                if (mid == 0 || total_weight(S - mid + 1, S) <= P) {
                    left_rooms = mid;
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        
        cout << left_rooms + right_rooms + 1 << "\n";
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。