Codeforces Round #621 (Div. 1 + Div. 2): D. Cow and Fields
問題
単純無向連結グラフ $G = (V, E)$ と部分集合 $S \subseteq V$ が与えられる。 異なる $2$ 頂点 $x, y \in S$ を選んでできるグラフ $G _ {x,y} = (V, E \cup \lbrace (x, y) \rbrace)$ 上の頂点 $1$ から頂点 $N$ への最短路長を $f(x, y)$ とする。 $\max _ {x, y \in S \wedge x \ne y} f(x, y)$ を求めよ。
解法
たぶん嘘
special な頂点の対 $(x, y)$ のいくつかを乱択 + heuristic で選んで試す。
それぞれの頂点 $v$ に対し始点からの距離 $s_v = d(1, v)$ と終点からの距離 $t_v = d(v, N)$ を求めておく。 special な頂点 $x, y$ をふたつ選んで使ったときの最短距離の値は $f(x, y) = \min \lbrace s_N, s_x + 1 + t_y, s_y + 1 + t_x \rbrace$ である。 答えは $\mathrm{ans} = \max \lbrace f(x, y) \mid x, y ~\text{are special}~ \wedge x \ne y \rbrace$ であるので、正解の対 $(x, y)$ を引ければよい。
とりあえず乱択する。$x, y$ 間に辺があれば正解確定なのでとりあえず確認しておく。 $s_x, s_y$ や $t_x, t_y$ が近い対 $(x, y)$ は正解に近い気がするのでこれも見ておく。 なぜか通る。
想定解
$s_x - t_y$ でソートして実家ぽく。計算量は BFS とソートが効いて $O(m + k \log k)$。
$f(x, y)$ の代わりに $g(x, y) = \min \lbrace s_x + t_y, s_y + t_x \rbrace$ を考えても同じである。 $\max g(x, y)$ を求れば $\mathrm{ans}$ も求まる。 そして $x, y$ の順序について、一般性を失うことなく $s_x + t_y \le s_y + t_x$ と仮定してよい。 つまり $\max \lbrace s_x + t_y \mid x, y \in S \wedge x \ne y \wedge s_x + t_y \le s_y + t_x \rbrace$ を求める問題に帰着された。
さて条件 $s_x + t_y \le s_y + t_x$ は $s_x - t_x \le s_y - t_y$ と同値である。 つまり $h(x) = s_x - t_x$ でソートし $h(x) \le h(y)$ な順序対 $(x, y)$ だけ考えればよい。 さて $h(x)$ の昇順に並べた $i$ 番目の頂点 $y$ まで見たとき $y$ は、$0, 1, \dots, i - 1$ 番目の頂点の中で最も $s_x$ の大きい $x$ と対にすればよい。 つまり $\max \left\lbrace \max \lbrace s_x \mid h(x) \le h(y) \wedge x \ne y \rbrace + t_y \mid y \in S \right\rbrace$ を計算する。 なお $h(x) = h(y)$ な組 $(x, y)$ については $s_x + t_y = s_y + t_x$ なのでその順序は気にしなくてよい。
メモ
Dは、各特殊頂点ごとに、スタートからの最短距離と、ゴールからの最短距離を求めると、順序がちょうど逆向きになっている場合だけを考えればよくて(そうでない場合はもともとの最短距離が答)以下略。
— tarattata (@tarattata1) February 17, 2020
理由:2つの特殊頂点a,b について、以下のような場合には、aとbを結んでも最短距離が変わらないことがわかる。
— tarattata (@tarattata1) February 17, 2020
(1)スタートからa,bまでの距離の差が1以内のとき
(2)ゴールからa,bまでの距離の差が1以内のとき
(3)スタートからa,bまでの距離の大小関係と、ゴールからa,bまでの大小関係が同じとき
D、こういう考察でZabuton的なソートをした pic.twitter.com/UgQMsl2dBO
— アルメリア (@armeria_betrue) February 17, 2020
そのテクニックを初めて見た問題を親だと認識するので私の中ではずっとZabutonソートって呼んでいる
— アルメリア (@armeria_betrue) February 17, 2020