ABC 319 E — Bus Stops

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Bus Stops の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 剰余周期と指数法則を利用する

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 剰余周期・指数法則

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: 剰余周期と指数法則を利用する

      • 剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。

      先に読む単元:

      この解説で扱わないこと:

      • 逆元・一次合同・CRTによる合同条件の統合、および巡回群の位数を使う計数。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題