ABC 401-500/ABC426E - Closest Moment - 競技プログラミング用 知識集積所

---

問題

ABC426E

必要知識

B以下レベルの内容は省略

• ベクトル（幾何学）※

別解の場合

• 三分探索※

考え方

まず、この問題には、話をややこしている要因が2つある。

1つめは、先に止まるのが高橋君か青木君かわからない点。
これは、2人の移動距離を計算し、青木君の移動距離の方が短ければ2人のデータをswap()※することで、高橋君が先に止まる、または同時に止まる前提で考えることができる。

2つめは、両者が動くと距離の式がややこしくなる点。
これは、相対座標を取ることで、高橋君を実質的に原点に固定して対応する。

スタートのときの相対位置をA、高橋君が止まるときの相対位置をB、青木君が止まるときの相対位置をCとすると、結局折れ線ABCの原点からの距離の最小値を取ればよい。
ただし、Bの青木君の座標は、実際に青木君を必要な時間動かしてみて座標計算をする。

原点に最も近い点の候補は

• 点A
• 原点から線分ABにおろした垂線の足（AB間にあった場合）
• 点B
• 原点から線分BCにおろした垂線の足（BC間にあった場合）
• 点C

の最大5か所。

点A,B,Cへの距離は普通にユークリッド距離※を計算すればよい。
垂線の足の方は、ベクトル（幾何学）※を参照しながら、間にある判定と、距離の計算を行う。
これらの最小値を答えればよい。

解答例

解答例

注意点

別解

三分探索※を行う

時刻tから2人の距離を求める関数を実装し、三分探索※をしてもよい。
三分探索※は「途中までは減少し、途中から増加する」「常に減少」「常に増加」のいずれかに当てはまるものにしか適用できない。
そのため、全体に対して用いることはできないが、「最初から1人目が止まるまで」「1人目が止まってから2人目が止まるまで」とわければそれぞれに三分探索※が適用できる。
よって、三分探索※を2回やり、最小値が小さかった方を答えればよい。
解答例