D - 通路の扉と体力 / Corridor Doors and Hit Points Editorial by admin Editorial for printing
gpt-5.5-xhigh概要
各質問の時刻 \(T_j\) における扉の重さを固定し、部屋 \(S_j\) から体力 \(P_j\) 以内で到達できる部屋の個数を求めます。
扉を直接列挙すると \(L\) が最大 \(10^9\) なので不可能です。代わりに「左端から各部屋までにある扉の重さの累積和」を使い、到達可能な部屋の範囲を二分探索で求めます。
考察
時刻 \(T\) を固定して考えます。
警備パターン \(i\) が錠をかける扉は、
\[ x \equiv R_i + V_i T \pmod{A_i} \]
を満たす扉です。
ここで、
\[ r_i = (R_i + V_i T) \bmod A_i \]
とします。
扉番号は \(1\) 以上なので、最初に錠がかかる扉は次のようになります。
- \(r_i \neq 0\) のとき：扉 \(r_i\)
- \(r_i = 0\) のとき：扉 \(A_i\)
つまり、最初の扉を \(\mathrm{first}_i\) とすると、その後は
\[ \mathrm{first}_i,\ \mathrm{first}_i + A_i,\ \mathrm{first}_i + 2A_i,\ \dots \]
という等差数列になります。
例えば \(A_i = 3,\ r_i = 2\) なら、錠がかかる扉は
\[ 2, 5, 8, 11, \dots \]
です。
次に、関数 \(F(p)\) を次のように定義します。
\[ F(p) = \text{扉 }1\text{ から扉 }p\text{ までの重さの合計} \]
つまり、部屋 \(0\) から部屋 \(p\) まで移動するときに通る扉の重さの合計です。
パターン \(i\) が扉 \(1\) から \(p\) までに錠をかける個数は、
\[ \begin{cases} 0 & (p < \mathrm{first}_i) \\ \left\lfloor \dfrac{p - \mathrm{first}_i}{A_i} \right\rfloor + 1 & (p \geq \mathrm{first}_i) \end{cases} \]
です。
これを全パターンについて足し合わせれば \(F(p)\) が求められます。
部屋 \(S\) から部屋 \(c\) に移動するときの消費体力を考えます。
- \(c > S\) のとき、通る扉は \(S+1, S+2, \dots, c\) なので、消費体力は
\[ F(c) - F(S) \]
- \(c < S\) のとき、通る扉は \(c+1, c+2, \dots, S\) なので、消費体力は
\[ F(S) - F(c) \]
したがって、どちらの場合も消費体力は
\[ |F(c) - F(S)| \]
です。
よって、部屋 \(c\) に到達できる条件は
\[ |F(c) - F(S)| \leq P \]
です。
これは次の条件と同じです。
\[ F(S) - P \leq F(c) \leq F(S) + P \]
ここで \(F(c)\) は \(c\) が大きくなるほど減らない、つまり単調非減少です。
そのため、条件を満たす部屋 \(c\) は連続した区間になります。
この区間の左端と右端を二分探索で求めればよいです。
素朴に各部屋や各扉を調べると \(L\) が最大 \(10^9\) なので間に合いませんが、この方法なら \(L\) に対しては \(\log L\) だけで済みます。
アルゴリズム
各質問ごとに以下を行います。
- 時刻 \(T\) における各警備パターンの最初の扉 \(\mathrm{first}_i\) を求める。
$\( r_i = (R_i + V_i T) \bmod A_i \)$
として、
$\( \mathrm{first}_i = \begin{cases} A_i & (r_i = 0) \\ r_i & (r_i \neq 0) \end{cases} \)$
- 関数 \(F(p)\) を計算できるようにする。
コードでは prefix_sum(pos) が \(F(pos)\) を計算しています。
- 現在地 \(S\) に対して、
$\( center = F(S) \)$
とする。
- 到達可能な部屋 \(c\) は
$\( center - P \leq F(c) \leq center + P \)$
を満たす。
そこで、
- \(F(c) \geq center - P\) を初めて満たす部屋を
left - \(F(c) \leq center + P\) を最後に満たす部屋を
right
として、それぞれ二分探索で求める。
- 答えは
$\( right - left + 1 \)$
である。
計算量
- 時間計算量: \(O(NQ \log L)\)
- 空間計算量: \(O(N)\)
各質問で、\(F(p)\) の計算に \(O(N)\) かかります。
二分探索は \(O(\log L)\) 回 \(F(p)\) を呼び出すため、1 質問あたり \(O(N \log L)\) です。
制約で \(N \times Q \leq 3 \times 10^5\) なので、十分高速に動作します。
実装のポイント
- 扉番号は \(1\) から始まるため、剰余が \(0\) のときの最初の扉は \(0\) ではなく \(A_i\) です。
first[i] = (r == 0 ? A[i] : r);
\(F(p)\) は単調非減少なので、二分探索が使えます。
\(V_i \times T\) は大きくなる可能性があるため、コードでは
__int128を使って安全に計算しています。
long long r = (long long)(((__int128)V[i] * T + R[i]) % A[i]);
累積和や体力は \(10^{14}\) 程度になるため、
long longを使います。ソースコード
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, L, Q;
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];
}
vector<long long> first(N);
auto prefix_sum = [&](int pos) -> long long {
long long res = 0;
long long p = pos;
for (int i = 0; i < N; i++) {
if (first[i] <= p) {
res += (p - first[i]) / A[i] + 1;
}
}
return res;
};
while (Q--) {
long long T, P;
int S;
cin >> T >> S >> P;
for (int i = 0; i < N; i++) {
long long r = (long long)(((__int128)V[i] * T + R[i]) % A[i]);
first[i] = (r == 0 ? A[i] : r);
}
long long center = prefix_sum(S);
long long low = center - P;
long long high = center + P;
int l = 0, r = L - 1;
while (l < r) {
int m = (l + r) / 2;
if (prefix_sum(m) >= low) r = m;
else l = m + 1;
}
int left = l;
l = 0;
r = L - 1;
while (l < r) {
int m = (l + r + 1) / 2;
if (prefix_sum(m) <= high) l = m;
else r = m - 1;
}
int right = l;
cout << right - left + 1 << '\n';
}
return 0;
}
この解説は gpt-5.5-xhigh によって生成されました。
posted:
last update: