Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 257 D問題 Jumping Takahashi 2

AtCoder ABC ABC257 D問題 400 pts

問題

提出解答

問題の概要

座標平面上に $N$ 点 $A_1, \dots, A_N$ があり, $A_i$ の座標は $(x_i, y_i)$ である. ジャンプ力が $S$ のとき, 以下の条件を満たす場合に限り点 $A_i$ から点 $A_j$ へ移動できる.

$P_i \times S \geq \left|x_i-x_j \right|+\left|y_i-y_j \right|$

適切に最初に $N$ 個の点から始点とする点を 1個選び, ジャンプ力を設定することにより, 始点から任意の点へ何回かの移動で到達できるようにしたい.

このとき, 設定すべきジャンプ力の最小値を求めよ.

制約

$1 \leq N \leq 200$
$-10^9 \leq x_i, y_i \leq 10^9$
$1 \leq P_i \leq 10^9$
$(x_i, y_i) \neq (x_j, y_j)$

解法

点 $i$ から点 $j$ へ移動するために必要な最低限度のジャンプ力は $i,j$ のみから決定され, $N \leq 200$ なので, 全ての $(i,j)$ に対して前計算で計算できる.

このとき, 始点 $A_I$ から始めるとする. このとき, 始点 $I$ から点 $A_j$ へ移動するために必要な最小のジャンプ力 $T_{I,j}$ は Dijstra 法を応用することで求めることができる *1. このとき, $\displaystyle U_I:=\max_{j=1,2, \dots, N} T_{I,j}$ が始点 $A_I$ から始める場合における必要な最小のジャンプ力である.

従って, 求めるべきは

$\displaystyle \min_{I=1,2, \dots, N} U_I=\min_{I=1,,2 \dots, N} \left(\max_{j=1,2, \dots, N} T_{I,j} \right)$

である. 各 $U_I$ を求めるために, Dijkstra 法 (Heap を使わない単純な) で時間計算量 $O(N^2)$ で求める事ができるので, $O(N^3)$ で正解を求めることができる.

*1:このようにできる理由: 最適な点 $A_I$ から点 $A_j$ への移動の途中に点 $A_k$ を経由する場合, $T_{I,j} \geq T_{I,k}$ が成り立つから