考察
stop iへ時刻xで着くと、次のdepartureはceil(x/P_i)P_iで、次stop到着はその値+T_iと一意に決まる。
全P_iは1..8なので、その公倍数L=lcm(1,..,8)=840だけ出発時刻をずらすと、各stopで待ち時間が同じになり到着時刻もLだけずれる。
したがって家を出てからの所要時間は出発時刻mod 840だけで決まり、Q queryに共通の840通りを前計算できる。
採用する候補: 出発時刻r=0..839を全routeでsimulationして所要時間を保存し、queryをq mod 840で参照する。
N本のroute計算を840回に限定し、各queryは定数時間で到着時刻へ戻せる。
棄却する候補: 各queryごとにN-1本のbusを順にsimulationする。
N≤10^5,Q≤2×10^5でNQ遷移になる。
棄却する候補: P_iの最大値8を周期として扱う。
例えばP=3とP=8が混在すると8だけのshiftではdeparture residueが保存されず、共通周期は公倍数でなければならない。
xとx+Lは各P_iで同じremainderを持つため、ceil待ちの増分は常にLで、区間ごとの所要時間差は0になる。
前計算値は絶対到着時刻ではなくelapsed[r]=arrival(r)-rとして持つと、任意qの答えをq+elapsed[q mod L]で得られる。
L=840とする。各r=0..L-1についてtime=r+Xから始め、i=1..N-1でtime=((time+P_i-1)/P_i)P_i+T_i、最後にYを加え、elapsed[r]=time-rを保存する。各query qにはq+elapsed[q%L]を64bitで出力する。
典型の発動条件
小LCMによる周期前計算
発動条件: 遷移が小さいmodulus群への丸めで決まり、そのLCMが小さいとき。
全840 residueのroute所要時間だけをsimulationする。
時刻表の切上げ遷移
発動条件: 周期Pの次eventを到着時刻xから求めるとき。
(x+P-1)/P·Pで最初のdepartureへ丸める。
問題固有の要素
絶対時刻はLずつ増えても、各bus区間の待ち時間と乗車時間は完全に同じなので、周期的なのはarrivalそのものではなくelapsed timeである。
別の問題へ持ち帰る視点: shift equivariantなsimulationでは、出力から入力shiftを引いた量が有限residueだけに依存しないか調べる。
正当性
timeを840だけずらすと各P_iの余りが等しく待ち時間が同じで、次stop到着も840だけずれる。全stopへ帰納適用するとarrival(q+840)=arrival(q)+840。従ってelapsed=arrival(q)−qはq mod840だけで決まり、全queryを前計算表から正確に復元できる。
実装上の注意
- ceil divisionは到着時刻がちょうどP_iの倍数なら待ち時間0になる式を使う。
- T_iの累積やquery時刻を含む到着時刻は32bitを超えるため64bit整数で持つ。
復習の核
- P=3,8を含む短いrouteでrとr+840を並行simulationし、各待ち時間が等しく絶対到着だけ840ずれることを確認する。
計算量と制約
時間
O(840N+Q)。全periodのLCM840に対する残余だけ前計算。
空間
O(840+N+Q)、query逐次出力ならO(840+N)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 10^5; 1 \leq X, Y \leq 10^9; 1 \leq P_i \leq 8; 1 \leq T_i \leq 10^9; 1 \leq Q \leq 2 \times 10^5; 0 \leq q_i \leq 10^9; All input values are integers.
出典