ABC 258 F — Main Street

考察

大通りへの入口を遠くまで探す必要はない。上下左右の直近の大通りへまっすぐ入り、その後に安い大通り上で位置を調整すればよい。始点・終点の出入りをそれぞれ4候補へ絞り、その間の最短費用を座標から求める。

各移動は上下左右の1歩で、大通りに沿うと1秒、それ以外は KK 秒かかる。座標は 10910^9 まで広がるため、格子点を頂点としてDijkstra法を実行することはできない。一方、道路の配置は周期 BB で繰り返す。点の絶対的な位置より、近くの大通りとの位置関係に注目しよう。

大通りへの出入りを四射影へ絞る

まず、2点 a,ba,b のマンハッタン距離を

M(a,b)=∣ax−bx∣+∣ay−by∣M(a,b)=|a_x-b_x|+|a_y-b_y|

と書く。大通りの割引を数えず、最短歩数だけ通常道路として払う KM(S,G)K M(S,G) を最初の候補にする。大通りを経由しない最適経路があれば、この候補で拾える。

点 a=(x,y)a=(x,y) に対して、その座標を挟む大通りの座標を

x−=B⌊x/B⌋,x+=B⌈x/B⌉,y−=B⌊y/B⌋,y+=B⌈y/B⌉\begin{aligned} x_-&=B\lfloor x/B\rfloor,& x_+&=B\lceil x/B\rceil,\\ y_-&=B\lfloor y/B\rfloor,& y_+&=B\lceil y/B\rceil \end{aligned}

とする。ここで床は切り捨て、天井は切り上げを表す。上下左右への四射影の集合は

P(a)={(x−,y),(x+,y),(x,y−),(x,y+)}P(a)=\{(x_-,y),(x_+,y),(x,y_-),(x,y_+)\}

である。例えば B=3,a=(1,1)B=3,a=(1,1) なら、左・右・下・上の候補は (0,1),(3,1),(1,0),(1,3)(0,1),(3,1),(1,0),(1,3) になる。

なぜ、斜めにずれた位置から入る候補は不要なのか。大通りにない点から出発すると、最初の大通りは、その点を囲む正方形の四辺のどれかである。縦の辺へ向かうなら、先に横へ直進して射影へ入り、縦移動を大通り上へ回せる。縦移動の単価が KK から1へ下がるので損をしない。横の辺も同様で、終点側は経路を逆に見ればよい。

射影 p∈P(a)p\in P(a) までの出入り費用は KM(a,p)K M(a,p) と数える。点 aa が既に大通り上なら P(a)P(a) に aa 自身が含まれ、費用0で出入りできる。他の射影までの費用をこの式で過大に数えても、入口・出口を aa 自身とする候補があるので最適解を失わない。

大通り上の2点間を座標から評価する

入口 pp と出口 qq を固定し、その間の最短費用を C(p,q)C(p,q) とする。中央区間でも通常道路を使ってよい。まず、大通りだけでマンハッタン距離を達成できる場合を取り出す。どの1歩も1秒以上なので、距離を達成できればそれが最短である。

  • 同じ大通り上なら、その線上を直進する。
  • 少なくとも一方が交差点、すなわち両座標が BB の倍数なら、その点から縦・横のどちらにも大通りで出られる。他方が属する大通りまで進んで曲がればよい。
  • 一方が縦大通り、他方が横大通り上なら、両線の交点で曲がる。例えば px,qyp_x,q_y が BB の倍数なら (px,qy)(p_x,q_y) を経由する。
  • 両方が縦大通り上で、帯が異なるなら、両者の高さの間に横大通りがある。その横大通りの高さまで進み、横へ渡ってから残りを縦に進む。横大通り同士は座標を交換すれば同じである。

ここで縦大通り上の点の「帯」は、連続する横大通りの間の領域を指し、番号を ⌊y/B⌋\lfloor y/B\rfloor とする。交差点は先に処理するので、残る点は帯の内部にある。以上の場合には C(p,q)=M(p,q)C(p,q)=M(p,q) とする。

残るのは、異なる縦大通り上で同じ帯にある2点である。共通の帯番号を jj とし、

d=∣px−qx∣,t=py−jB,u=qy−jBd=|p_x-q_x|,\qquad t=p_y-jB,\qquad u=q_y-jB

と置く。t=py mod B,u=qy mod Bt=p_y\bmod B,u=q_y\bmod B は、それぞれ下側の横大通りからの高さである。横へ渡る方法を、次の3つに分ける。

  • 帯の内部を通常道路で横断する。 横の dd 歩を単価 KK で払い、縦のずれは大通り上で調整する。費用は Kd+∣t−u∣Kd+|t-u|。
  • 下側の横大通りを経由する。 高さ jBjB まで tt 歩下り、横へ dd 歩進んで uu 歩上る。費用は d+t+ud+t+u。
  • 上側の横大通りを経由する。 高さ (j+1)B(j+1)B まで B−tB-t 歩上り、横へ渡って B−uB-u 歩下る。費用は d+2B−t−ud+2B-t-u。

従って、中央区間の費用は

C(p,q)=min⁡(Kd+∣t−u∣,d+t+u,d+2B−t−u)\begin{aligned} C(p,q)=\min\bigl(&Kd+|t-u|,\\ &d+t+u,\\ &d+2B-t-u\bigr) \end{aligned}

となる。同じ帯の横大通り同士なら x,yx,y を交換し、左右の迂回として同じ式を使う。

例えば B=5,p=(0,2),q=(5,3)B=5,p=(0,2),q=(5,3) では d=5,t=2,u=3d=5,t=2,u=3 であり、通常横断・下迂回・上迂回は順に 5K+1,10,105K+1,10,10 秒となる。K=1K=1 なら通常横断の6秒、K=3K=3 なら大通りを回る10秒を選ぶ。大通り上の点同士でも、常に大通りだけを使うとは限らない。

16通りを全体の答えへつなぐ

始点の射影 p∈P(S)p\in P(S) と終点の射影 q∈P(G)q\in P(G) を全組合せし、各組の費用を次の和で求める。

F(p,q)=KM(S,p)+C(p,q)+KM(q,G)\begin{aligned} F(p,q)={}&K M(S,p)\\ &+C(p,q)\\ &+K M(q,G) \end{aligned}

答えを KM(S,G)K M(S,G) で初期化し、4入口×4出口の16通りの F(p,q)F(p,q) で最小値を更新すればよい。これで、直接移動と大通りを経由する全候補の最小値を取れる。無限平面を探索する代わりに、出入りの候補と中央区間の道路配置だけを調べられた。

典型の発動条件

境界候補の定数列挙

高速領域へ入る前の移動を、その領域に入った後へ移しても損をしないとき、入口を最近の境界へ寄せられる。今回は通常道路の縦・横移動を単価1の大通り上へ移せるので、四射影への列挙が使える。

「近い入口だけでよさそう」で止めず、任意の入口を残す候補へ置き換えた経路が高くならないことを示す。

周期格子上の距離場合分け

移動費用が位置で変わるときも、1歩の最小単価からマンハッタン距離の下界が得られる。まずその下界を達成する経路を構成し、達成できない位置関係だけを場合分けする。

今回は同じ帯の平行大通り間だけが例外となり、通常横断と両側の境界への迂回を比べる。周期があるだけでは十分ではなく、中央区間を定数個の経路で覆えることまで確かめる。

問題固有の要素

この道路配置では、縦・横の大通りが必ず交差する。異なる帯へ進むときには途中の横大通りを利用できるため、例外は同じ帯にある平行線間の移動だけになる。周期性に加え、この交差構造が中央区間を3候補へ絞る鍵である。

四射影への削減と中央区間の場合分けは個別公式解説に沿う。ここでは、その分岐を座標条件・距離式へ書き下し、以下で候補の網羅性を補う。

正当性

まず出入りの削減を示す。始点が大通り上にないとし、ある経路が初めて大通りに触れる点を rr とする。rr は始点を囲む正方形の辺上にある。縦の辺なら、同じ辺への射影 pp を先に通り、その大通り上を rr まで進めばよい。横移動の必要量は変わらず、縦移動の単価は KK から1へ下がるため、元の経路以下の費用で rr に着く。横の辺でも同様である。終点側も逆向きに置き換えられる。始点・終点が大通り上なら、その点自身を射影に選べばよい。

次に中央費用を示す。全移動の単価は1以上なので、C(p,q)≥M(p,q)C(p,q)\geq M(p,q) である。同じ大通り・交差点・異なる向き・異なる帯の各場合には、考察で構成した経路が大通りだけを使ってこの下界に一致する。

異なる縦大通り上で同じ帯にある場合は、任意の経路を横大通りに触れるかどうかで分ける。横大通りに触れなければ、横移動はすべて単価 KK で合計 dd 歩以上、縦移動は合計 ∣t−u∣|t-u| 歩以上なので、費用は Kd+∣t−u∣Kd+|t-u| 以上になる。この値は通常道路を横断し、縦のずれを縦大通り上で調整すれば達成できる。

横大通りに触れるなら、帯の下端か上端を少なくとも一度通る。下端を通る経路は縦移動が合計 t+ut+u 歩以上、上端を通る経路は 2B−t−u2B-t-u 歩以上必要である。さらに横移動が dd 歩以上必要なので、費用は対応する迂回候補以上となる。両候補とも大通りだけで実現できるため、この場合も3候補の最小値が厳密な中央費用である。横大通り同士は座標交換で同じ議論になる。

従って、大通りに触れる最適経路は、費用を増やさず16通りのいずれかへ置き換えられる。触れない最適経路は KM(S,G)K M(S,G) で覆える。一方、各候補にはその値以下の費用で移動する経路がある。出入りや直接移動を単価 KK で数える際に大通りを通れば、実費用はむしろ下がるだけである。よって候補の最小値は真の最適費用を下回らず、最適経路を覆う候補はそれを上回らないので、求める答えと一致する。

実装上の注意

  • 射影の座標、距離、費用の積・和は符号付き64ビット整数で計算する。直接候補だけでも 2×10182\times 10^{18} に達し得る。32ビットで積を計算してから64ビットへ代入するのでは遅い。
  • 非負座標では上側の倍数を ((x + B - 1) / B) * B という整数演算で求められる。元から倍数なら自分自身へ射影される。射影が重複しても16通りのまま調べてよい。
  • 先に同じ大通り・交差点・異なる向きを処理し、残った平行線について帯番号を比べる。縦大通り同士の帯は ⌊y/B⌋\lfloor y/B\rfloor、横大通り同士の帯は ⌊x/B⌋\lfloor x/B\rfloor である。剰余と帯番号の周期にはすべて BB を使う。
  • K=1K=1 では直接候補がマンハッタン距離に一致する。B=1B=1 では全道路が大通りなので中央費用は常にマンハッタン距離になる。S=GS=G なら直接候補が0を返す。

復習の核

  • 高価な移動を安い領域へ入った後に回せるなら、入口を最近の境界へ寄せる交換を考える。
  • 距離の下界を先に置き、それを達成できる位置関係と、迂回が必要な位置関係を分ける。
  • 「入口・出口が大通り上」と「その間も大通りだけを使う」は別である。同じ帯では通常横断と両側の迂回を比較する。

計算量と制約

時間

各テストケースで射影を各4点求め、16組の中央費用を定数回の整数演算で評価するので O(1)O(1)。全 TT ケースの入出力を含めて O(T)O(T)。

空間

各ケースを順に処理すれば、各4点の射影と費用だけを保持するため O(1)O(1) 補助領域。入力・出力を全ケース分まとめて保持する実装では、その領域は別に O(T)O(T) 必要となる。

制約との対応

公式制約は 1≤T≤2×1051\leq T\leq 2\times 10^5、1≤B,K≤1091\leq B,K\leq 10^9、0≤Sx,Sy,Gx,Gy≤1090\leq S_x,S_y,G_x,G_y\leq 10^9 で、入力はすべて整数。時間制限は3秒、メモリ制限は1024 MiB。座標や周期の大きさに依存する探索を行わず、各ケース16組だけを評価する。K≥1K\geq 1 が、出入りの交換とマンハッタン距離の下界を支える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Main Street の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 幾何の基本判定と座標変換

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

    主タグ: 幾何の基本判定・配置・座標変換

    補助タグ: 有界全列挙・有限case分解

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

    学習の位置

    体系上の位置: 幾何の基本判定と座標変換

    • 幾何条件を外積・距離式・端点順・格子占有・変換後座標の局所判定へ落とし込める。

    先に読む単元:

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

    • 凸包の境界候補列挙・半平面交差。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題