方針

各ロボットについて、「いつ起動するか」を求めます。

素朴には、起動したロボットから進行方向にあるロボットを探索し、最短到達時刻を更新するという処理を繰り返したいです。これをもって Dijkstra 法のようなアルゴリズムを行うことができますが、時間計算量が全体で \(O(N^2)\) となって間に合いません。

また、「あるロボットの進行方向にあるまだ起動していないロボットは、そのロボット自身が起動させる」とは限りません。反例が簡単に作れますが、少し見えにくいです。

グラフの工夫

そこで、グラフを少し工夫します。(座標, 方向) の組を状態として、それぞれの方向に対してベルトコンベアのように辺を伸ばします。（コストはかかる時間）

ここで、座標として必要な値は \((x_i,y_i)\) の \(N\) 種類のみであるので、状態数は \(4N\) 個です。

誰かが \(((x_i,y_i), z)\) という状態に到達したら、同時に「\((x_i,y_i)\) にいるロボットが起動していないなら起動する」というイベントが発生したとみなし、 \(((x_i,y_i), d_i)\) という状態にも重み \(0\) で到達します。

この工夫したグラフによって、ロボットの動き方が再現できます。

状態数と辺数はいずれも \(O(N)\) 個であるので、Dijkstra 法の亜種のアルゴリズムによって全体で \(O(N \log N)\) 時間で解けます。