考察
無限平面をBFSすることはできない。まずタイルの向きを揃え、遠方の繰り返し部分を除いて有限の境界問題へ帰着する。各座標は整数マスの左下なので、反転は点の中心の0.5も反映して行う。
次の手順で始点のタイルを横向きのblock (0,0)へ置き、終点blockの添字を非負にする。
- 始点blockが奇数parityで縦向きなら、両点へ(x,y)←(y,−x−1)を適用する。この90度回転でblockのparityが反転し、配置を保ったまま横向きになる。
- 始点のblock添字u=floor(S_x/K),v=floor(S_y/K)を求め、両点から(uK,vK)を引く。u+vは偶数なので配置は保存される。
- T_x<0なら両点のxをK−1−xへ、T_y<0なら両点のyをK−1−yへ反転する。始点はblock (0,0)内のままである。
横向き始点のタイル内番号s=S_y(0≤s<K)を得る。終点のblockはi=floor(T_x/K),j=floor(T_y/K)。終点タイル内番号はi+jが偶数ならk=T_y mod K、奇数ならk=T_x mod Kである。横長タイルの内部x座標は距離に影響しない。
i=j=0なら回答はmin(|s−k|,2)。同blockの隣接横タイルを順に移る道と、横隣の縦タイルを経由する二手の道を比較する。
表を作る前に、タイルの隣接を見る
Hは横長タイルK枚を縦に積むblock、Vは縦長タイルK枚を横に並べるblockである。番号0は下端(H)または左端(V)、K−1は上端または右端を表す。
x方向 →
y=1 V | H | V
y=0 H | V | H
0 1 2
H(0,0,s)から右のV(1,0,0)へはsによらず一手。そのVは上辺全体を持つため、さらに上のH(1,1,0)へ一手で移れる。この二手が対角方向の到達境界を一段広げる基本形である。向きを交換しても同じ形が繰り返され、右と上の二境界を越えるには少なくとも二手が要る。到達集合の右端・上端をこの形で伸ばすと、始点に近い(1,1)を除いて同じ局所番号への到達時刻が一段ごとに2ずれる。初回だけは始点のsと終点のkの接続費用が効くので、(1,1)を基底に残す。
軸方向では中央のVの左端から右端へ抜けたい。内部を横に進むとK−1手だが、上のHの最下タイルを経由すれば「V左端→H→V右端」の二手で済む。左右のHとの乗り換え各一手を加え、二block分の反復費用は2+min(K−1,2)。これがK=2では3、K≥3では4となる理由である。
基底表も同じ接続費用で読める。(1,0)へはVの左端へ一手、番号kまで内部をk手、または上下のH経由で二手なので1+min(k,2)。(0,1)へは始点Hの上端までmin(K−1−s,2)手、上のVへ一手なので1+min(K−1−s,2)。後者の二手の迂回は右のVを使う。K=3の(1,1)ではs=0,k=0は右→上の2手、s=0,k=1は最後にHを一段上がる3手になる。境界へ近づく費用が二手で飽和するため、遠方ではsとkを三段だけ残せばよい。同blockだけは直接の|s−k|も残す。
その他では次の縮約を行い、取り除いた距離をcostへ足す。
- i,j>0ならd=min(i,j)を取る。ただしi=jならdを1減らして(1,1)を残す。(i,j)←(i−d,j−d)、cost+=2d。
- その後i=0またはj=0ならn=max(i,j)、h=max(0,floor((n−2)/2))とする。非零の添字から2hを引き、K=2ならcost+=3h、それ以外ならcost+=4h。
最初の縮約は(i,j)≠(1,1)で両添字を1ずつ減らすと距離が2減る性質、次は軸上の添字n≥4を2減らすと距離がK=2で3、K≥3で4減る性質を使う。結果は(0,1),(0,2),(0,3),(1,0),(2,0),(3,0),(1,1)の七つだけになる。
K≥3ではs≤K−3の差は遠方への距離に影響せず、k≥2も同じである。s'=max(s,K−3)−(K−3)、k'=min(k,2)として、次の表のs'行・k'列(いずれも0,1,2)を読む。各行は角括弧内の三つの数、セミコロンで次の行へ進む。
K=2ではs,k∈{0,1}をそのまま行・列に使う。
回答はcostと基底距離の和。表は巨大座標を列挙した結果ではなく、境界からの0,1,2と向きだけを残した有限問題の距離である。
典型の発動条件
周期幾何の対称性・再帰縮約
発動条件: 巨大周期タイル上の最短距離で局所形が繰り返されるとき。
標準領域へ正規化し、一定距離を持つブロック移動を閉形式化する。
問題固有の要素
casework を座標値そのものではなく、距離が変わる境界までの飽和値と parity に整理する。
別の問題へ持ち帰る視点: 愚直 0-1 BFS は小座標の oracle として使い、有限ケース式の検証へ回す。
正当性
座標の対称変換はタイルの辺隣接を保つ。到達境界は考察の二手の対角移動と、中央blockを抜ける3手または4手の軸移動で周期的に伸びる。始点に接する例外を残してこの反復部分を剥がし、出入りの局所費用だけを基底表で計算する。境界への内部移動は隣block経由の二手に置き換えられるので三段への飽和が有効であり、同blockの場合は直接移動との最小を別に取る。よって縮約費用と残った局所距離を足せばよい。
実装上の注意
- 負座標のblock添字は数学的floor divisionで求める。中心座標の反転は−xではなく−x−1(回転)またはK−1−x(block反転)を使う。
- 対角縮約で(1,1)を残す。同blockケースにはs,kの飽和を使わず、元の|s−k|を評価する。
- K=2とK≥3の表を分ける。座標・縮約量・距離は64ビット整数。
復習の核
- 一般位置の (i,j)→(i-1,j-1)+2 をまず証明し、残った有限ケースは小範囲 BFS と全列挙比較する。
計算量と制約
時間
O(1)、正規化後に対角成分min(i,j)を一括除去して有限個の基底式へ落とす。
空間
O(1)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 10^4; 2 \leq K \leq 10^{16}; -10^{16} \leq S_x, S_y, T_x, T_y \leq 10^{16}; All input values are integers.
出典