E - Nearest Black Vertex Editorial by Kude
（追記）解説放送（1:26:45あたりから）でもこの解法が説明されました。以下の説明に不明な点があれば、こちらの動画も参照してみてください。
\(O(N + M)\) 解法です。 方針自体は公式解説と同じですが、それぞれの処理を工夫することで線形時間に落とせます。
解法は次の2ステップに分けられます。
- 「いずれかの \(i=1,2, \ldots ,K\) で頂点 \(p_i\) から距離が \(d_i\) 未満にある」ような頂点を全て見つける。
- 色を決めた時、それが条件を満たすような塗り方になっているかチェックする。
ステップ 2. は黒の頂点を始点とした多始点BFSをすればよいです。ステップ 1. を線形時間で処理するには以下のようにすればよいです。
2頂点 \(x, y\) の距離を \(\text{dist}(x, y)\) と表すことにします。頂点 \(v\) を白に塗らなければならない条件は次の通りです。
\[
\begin{aligned}
& \text{いずれかの} \, i=1,2, \ldots ,K \, \text{で} \, \text{dist}(v, p_i) < d_i \, \text{が成立} \\
\Leftrightarrow\, & \text{いずれかの} \, i=1,2, \ldots ,K \, \text{で} \, \text{dist}(v, p_i) - d_i < 0 \, \text{が成立} \\
\Leftrightarrow\, &\min_{i=1,2, \ldots ,K} (\text{dist}(v, p_i) - d_i) < 0
\end{aligned}
\]
したがって、各頂点 \(v\) について \(\displaystyle t_v \coloneqq \min_{i=1,2, \ldots ,K} (\text{dist}(v, p_i) - d_i)\) が求まればよいです。BFSによる距離計算と同じ要領で、\(t_v\) の値は小さい方から順に求めていくことができます。
posted:
last update: