Kazun の競プロ記録

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

AtCoder Beginner Contest 237 E 問題 Skiing

AtCoder ABC ABC237 E問題 500 pts

問題

提出解答

問題の概要

スキー場には $N$ 個の広場があり, 広場 $i$ の標高は $H_i$ である. また, $M$ 個の坂があり, 広場 $U_j$ と広場 $V_j$ を双方向に行き来可能にする.

この坂でのみ広場を移動でき, 標高が $S$ である広場から, 広場 $T$ である広場へ坂を利用して移動した場合, 以下のようにして楽しさが変化する.

$S \geq T$ ならば, 楽しさが $S-T$ だけ増加する.
$S \lt T$ ならば, 楽しさが $2(T-S)$ だけ減少する.

最初, 広場 $1$ にいるとする. ここから $0$ 本以上の坂を利用して移動を繰り返した場合の楽しさの最大値を求めよ.

制約

$2 \leq N \leq 2 \times 10^5$
$N-1 \leq M \leq \min \left(2 \times 10^5, \frac{N(N-1)}{2} \right)$
$0 \leq H_i \leq 10^8$
$1 \leq U_j \lt V_j \leq N$
$j \neq k \Rightarrow (U_j, V_j) \neq (U_k, V_k)$
どの $2$ の広場もいくつかの坂を利用して移動できる.

解法

移動した際の楽しさの増減値から, 広場 $k$ で移動を終えた場合の楽しさは $H_1-H_k-({\text 登った高さの総和})$ になる. $k$ を固定すると, 登った高さの総和を最小化する問題になる. よって, 次の問題を解くことになる.

重み付き有向グラフ $D=(V=[\![N]\!], A, C)$ がある. ただし,

$A=\left\{\overrightarrow{U_j V_j} \mid j=1,2, \dots, M \right\} \cup \left\{\overrightarrow{V_j U_j} \mid j=1,2, \dots, M \right\}$
$C: A \to \mathbb{R}; \overrightarrow{uv} \mapsto \begin{cases} 0 & (H_u \geq H_v) \\ H_v-H_u & (H_u \lt H_v) \end{cases}$

とする. $k=1,2, \dots, N$ 全てに対して, 頂点 $1$ から頂点 $k$ への最小コスト $X_k$ を求めよ.

この問題は Dijkstra 法で解くことになる. そして, 答えは

$\displaystyle \max_{k=1,2, \dots, N} \left(H_1-H_k-X_k \right)$

である. Dijkstra 法の計算量は $O((N+M) \log N)$ であり, 十分高速である.