ABC 426 E — Closest Moment

考察

二人はいずれも線分上を単位速度で進み、短い方が到着した後だけ一人が動く。長い移動時間 p と短い移動時間 q に揃えると、距離ベクトルは各時間区間で一次関数になる。

採用する候補: p≥q となるよう二人を交換し、同時移動区間 [0,q] と一人だけ動く区間 [q,p] をそれぞれ原点と線分の最短距離へ帰着する。

各フェーズの相対位置が線分を動く点となり、点と線分の距離を定数時間で求められる。

棄却する候補: 時刻全体を細かく刻んで二人の距離をサンプリングする。

連続時刻の真の最小値を保証できず、刻み幅による誤差管理も不要に難しい。

同時移動中の相対位置は (A-C)+(t/q)((E-A)-(D-C)) であり、t/q∈[0,1] に対して一つの線分を描く。

一人の到着後は、動く側の線分 EB と停止点 D の距離を求めればよい。

p<q なら人物を入れ替える。時刻 q の長い側の位置 E=A+(q/p)(B-A) を求め、相対位置の端点 A-C と E-D を結ぶ線分から原点への距離、および線分 EB から D への距離の小さい方を返す。

典型の発動条件

相対運動

発動条件: 複数点が同時に等速直線運動し、その距離の最小値を求めるとき。

一方から他方を引いた相対位置を考え、時間に対する一本の線分へ変換する。

点と線分の距離

発動条件: 連続パラメータ上の一次ベクトルのノルムを最小化するとき。

射影係数を [0,1] に clamp して最近点を求めるか、凸性を用いた三分探索で評価する。

問題固有の要素

停止時刻で区切ることで、速度が変わる運動も二本の相対位置線分だけに整理できる。

別の問題へ持ち帰る視点: 連続時間の等速運動では座標を個別追跡せず、相対位置が描く幾何図形を見る。

正当性

到着時刻順に区間を分けると相対位置は各区間で一次関数なので、距離最小は原点とその相対segmentの最短距離に等しい。同時移動区間の端相対位置と停止後の移動segmentを求めれば全時刻を覆う。segmentへの射影を[0,1]にclampすることで区間外の最小点を除き、二区間最小を取ると全時刻最小になる。

実装上の注意

  • 長さ 0 の線分では除算を避けて端点距離を使う。浮動小数の出力精度と、p<q の人物交換後の座標対応に注意する。

復習の核

  • 時刻 q の E が長い側の移動比 q/p で計算されているか、両フェーズの端点が時刻 q で連続するかを確認する。

計算量と制約

時間

各case O(1)。同時移動と片方停止の二segment距離。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1\leq T\leq 2\times 10^5; -100\leq TS_X,TS_Y,TG_X,TG_Y,AS_X,AS_Y,AG_X,AG_Y \leq 100; (TS_X,TS_Y)\neq (TG_X,TG_Y); (AS_X,AS_Y)\neq (AG_X,AG_Y); All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Closest Moment の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

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

      学習の位置

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

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

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

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

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題