ABC 382 G — Tile Distance 3

考察

無限平面をBFSすることはできない。まずタイルの向きを揃え、遠方の繰り返し部分を除いて有限の境界問題へ帰着する。各座標は整数マスの左下なので、反転は点の中心の0.5も反映して行う。

次の手順で始点のタイルを横向きのblock (0,0)へ置き、終点blockの添字を非負にする。

  1. 始点blockが奇数parityで縦向きなら、両点へ(x,y)←(y,−x−1)を適用する。この90度回転でblockのparityが反転し、配置を保ったまま横向きになる。
  2. 始点のblock添字u=floor(S_x/K),v=floor(S_y/K)を求め、両点から(uK,vK)を引く。u+vは偶数なので配置は保存される。
  3. 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)を読む。各行は角括弧内の三つの数、セミコロンで次の行へ進む。

終点blockK≥3の基底距離行列
(0,1)[3,3,3]; [2,2,2]; [1,1,1]
(0,2)[4,5,6]; [3,4,5]; [2,3,4]
(0,3)[7,7,7]; [6,6,6]; [5,5,5]
(1,0)[1,2,3]; [1,2,3]; [1,2,3]
(2,0)[4,4,4]; [4,4,4]; [4,4,4]
(3,0)[5,6,7]; [5,6,7]; [5,6,7]
(1,1)[2,3,4]; [2,3,3]; [2,2,2]

K=2ではs,k∈{0,1}をそのまま行・列に使う。

終点blockK=2の基底距離行列
(0,1)[2,2]; [1,1]
(0,2)[3,4]; [2,3]
(0,3)[5,5]; [4,4]
(1,0)[1,2]; [1,2]
(2,0)[3,3]; [3,3]
(3,0)[4,5]; [4,5]
(1,1)[2,3]; [2,2]

回答は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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Tile Distance 3 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 同値な状態を正規化する

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

      主タグ: 状態・配置の正規化

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

      学習の位置

      体系上の位置: 同値な状態を正規化する

      • 対称操作で同値な状態の標準形と不変量を選べる。

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

      • 交換論による貪欲順の証明。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題