Kazun の競プロ記録

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

AtCoder Beginner Contest 286 E問題 Souvenir

AtCoder ABC286 ABC E問題 500 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 個の都市がある. $S_i$ の $j$ 文字目が ${\tt Y}$ ならば, 都市 $i$ から都市 $j$ への直行便が存在し, ${\tt N}$ ならば存在しない.

また, 都市 $i$ では価値が $A_i$ であるお土産がある.

以下の $Q$ 個の問について答えよ.

問 $q$

都市 $U_q$ から都市 $V_q$ へいくつかの直行便を利用することによって, 移動することは可能か?

また, 可能ならば, 以下を満たすような移動の方法における「利用する直行便の数」と「購入したお土産の価値の総和」を答えよ.

都市 $U_q$ から都市 $V_q$ への移動の方法のうち, 利用する直行便の数が最小である.
上を満たすような移動の方法のうち, 都市 $U_q$ と都市 $V_q$ を含める経由する都市全てでお土産を $1$ 個ずつ購入した場合における購入したお土産の価値の総和

制約

$1 \leq N \leq 300$
$1 \leq A_i \leq 10^9$
$S_i$ は ${\tt Y}, {\tt N}$ からなる長さ $N$ の文字列
$1 \leq Q \leq N(N-1)$
$1 \leq U_q, V_q \leq N$
$U_q \neq V_q$
$q \neq r \Rightarrow (U_q, V_q) \neq (U_r, V_r)$

解法

$\mathbb{N}$ を非負整数全体の集合とする. 代数系 $F$ を次のようにして定義する.

$F:= (\mathbb{N} \cup \{+\infty \}) \times \mathbb{N}$
$(a,b), (a', b')$ に対して, $(a,b)+(a',b'):=(a+a', b+b')$

また, $E$ における順序を次のように設定する.

$(a,b) \leq (a', b') : \iff (a \lt a') \lor (a=a' \land b' \geq b)$

このとき, $F$ は $(0,0)$ を単位元として持つ. また, $F$ は以下を満たす全順序である.

$a,b,c \in F$ に対して, $a \leq b$ ならば, $a+c \leq b+c$ である.

よって, この問題は次のような問題に帰着される.

次のようにして定義される重み付き有向グラフ $D=(V,E,C: E \to F)$ がある.

$V:=\{1,2, \dots, N\}$
$E:=\{\overrightarrow{uv} \mid S_{u,v}={\tt Y} \}$
$C(e):=(1, A_v)$

このとき, $U_q$ から $V_q$ へ到達可能か? 可能ならばその有向パスにある重みの総和の最小を求めよ.

この問題における重みを最小にするパスが $F$ の定義から要求を満たす有向パスであることがわかる.

この重み付きグラフにおいて, Warshall-Floyd 法を利用することにより, 任意の $2$ 頂点間において, その2頂点間の有向パスが存在するか? 存在するならばその重みの最小値を求めることができる.

これにより, 前計算 $O(N^3)$ 時間, $1$ 問当たり $O(1)$ 時間で求めることができ, 合計でO(N^3+Q)] 時間で解くことができる.

なお, 問題に答える際, $D$ の重みの設定から, 開始点におけるお土産の価値を加算していないので, 答える際にその分を加算することを忘れないこと.