Kazun の競プロ記録

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

AtCoder Beginner Contest 274 E問題 Booster

AtCoder ABC274 ABC E問題 500 pts

問題

提出解答

問題の概要

2次元座標上に $N$ 個の街と $M$ 個のブースターがある. $i$ 番目の街は座標 $(X_i, Y_i)$ にあり, $j$ 番目のブースターは $(P_j, Q_j)$ にある.

ブースターを $1$ 個獲得するごとに移動速度が $2$ 倍になる.

最初, 原点にいる高橋君が全ての街を訪れ, 原点に戻るような移動の方法において, 所要時間の最小値を求めよ (ブースターは全て取得しなくても良い).

制約

$1 \leq N \leq 12$
$1 \leq M \leq 5$
$-10^9 \leq X_i, Y_i, P_j, Q_j \leq 10^9$
$(0,0), (X_i, Y_i), (P_j, Q_j)$ は互いに異なる.

解法

$X$ を原点, 街, ブースターのある地点からなる $(N+M+1)$ 要素の集合とし, $B$ をブースターのある地点からなる $X$ の部分集合とする.

bitDP による動的計画法を考える. $X$ の部分集合 $S$ と $a \in S$ に対して, ${\rm DP}[S,a]$ を

$S$ を全て訪れ, 最後に訪れるのが $a$ であるような移動の方法における最小値.

ベースケースは原点をスタート, ゴールにしたいので, 原点を ${\rm O}$ として, 便宜上次のようにする.

${\rm DP}[\emptyset, a]=\begin{cases} 0 & (a={\rm O}) \\ \infty & (a \neq {\rm O}) \end{cases}$

更新式について, 座標平面は距離について三角不等式を満たすことに注意すると, 1度訪れた地点を再び訪れるメリットはない. よって, $v \in S, w \in X \setminus S$ に対して, $S$ の時点で獲得しているブースターの数は $\#(S \cap B)$ で計算できる.

このことに注意すると,

${\rm DP}[S \cup \{w\}, w] \xleftarrow{\min} {\rm DP}[S,v] + \dfrac{\operatorname{dist}(v,w)}{2^{\# (S \cap B)}}$

である.

これにより, 求めるべき解答は街と原点全体の集合を $T$ とすると,

$\displaystyle \min_{T \subset S \subset X} {\rm DP}[T,{\rm O}]$

になる.