ARC152B 精進メモ - こゃーその雑記

問題

思考過程

2人のスタートする位置と向きさえ決めれば、あとの動きは決まりそう。ただ、このままだと初期状態が $O(N^2)$ 通りあるので、間に合わない。

図を書いてみると、交差点は2つになっていそうなので、この交差する場所をうまく選んであげれば行けそう。

多分初期位置によらずに交差するのは（時間的に最後を除いて）2つだろう思われる（未証明）ので、
最初に交差する地点を決めてシミュレーションレーションができそう。これだと場合の数は $N$ で済むので。

次に出発してから交差する休憩所を決める。シミュレーションについて、愚直に端から位置を求めようとすると、各シミュレーションごとに $O(N)$ かかってしまい、全体で $O(N^2)$ になってしまうので間に合わない。なので工夫を考える。

よく考えると、なるべく休憩所で待つ時間が少ない方がいいので、道上ですれ違う直前/直後の休憩所で待つほうが良い。なので、交差する瞬間の位置を求める。時間自体は距離と等しいので、簡単に求められるので、「出発して折り返してから、二人のどちらが先についているか」というもので二分探索できる。

そこまでいったら、休憩する場所の2箇所でどのぐらい時間がかかるかを求めればいい。色々整理すると、 $i$ 番目の休憩所から出発して途中 $j$ 番目の休憩所で待機する時間は、「 $i$ 番目の休憩所から左右のどちらかの端に行って $j$ 番目の休憩所にいくまでのかかる時間の大きい方」＋「 $j$ 番目の休憩所から左右のどちらかの端に行って $i$ 番目の休憩所にいくまでのかかる時間の大きい方」になる。これなら全体で $O(NlogN)$ で済むので間に合いそう。