コンテストでの時間切れや解けなかった過去問を振り返って供養していく

11/2: AtCoder Beginer Contest 178 E - Dist Max

供養

問題

Difficulty: 1043 (記事作成時点)

マンハッタン距離の式を式変形すると以下のようになる \begin{array}{ll} &|x_{i} - x_{j}| + |y_{i} - y_{j}|\\ =&\mathrm{max}(x_{i} - x_{j}, x_{j} - x_{i}) + \mathrm{max}(y_{i} - y_{j}, y_{j} - y_{i})\\ =&\mathrm{max}(x_{i} - x_{j} + y_{i} - y_{j}, x_{i} - x_{j} + y_{j} - y_{i},\\ &x_{j} - x_{i} + y_{i} - y_{j}, x_{j} - x_{i} + y_{j} - y_{i})\\ =&\mathrm{max}( (x_{i} + y_{i}) - (x_{j} + y_{j}), (x_{i} - y_{i}) - (x_{j} - y_{j}),\\ &(x_{j} - y_{j}) - (x_{i} - y_{i}), (x_{j} + y_{j}) - (x_{i} + y_{i})) \end{array}
ここで $z_{i} = x_{i} + y_{i}, w_{i} = x_{i} - y_{i}$ とすると、上式はさらに以下のようになる \begin{array}{ll} &\dots\\ =&\mathrm{max}(z_{i} - z_{j}, w_{i} - w_{j}, w_{j} - w_{i}, z_{j} - z_{i}) \end{array}
上式から、任意の $i, j$ についてのマンハッタン距離の最大値は以下のように求められる \begin{array}{ll} &\underset{i, j}{\mathrm{max}}(|x_{i} - x_{j}| + |y_{i} - y_{j}|)\\ =&\underset{i, j}{\mathrm{max}}(\mathrm{max}(z_{i} - z_{j}, w_{i} - w_{j}, w_{j} - w_{i}, z_{j} - z_{i}))\\ =&\mathrm{max}(\underset{i}{\mathrm{max}}(z_{i}) - \underset{i}{\mathrm{min}}(z_{i}), \underset{i}{\mathrm{max}}(w_{i}) - \underset{i}{\mathrm{min}}(w_{i})) \end{array}

実装は

各 $(x_{i}, y_{i})$ について、$z_{i} = x_{i} + y_{i}, w_{i} = x_{i} - y_{i}$ とする
$\mathrm{max}(\mathrm{max}(z_{i}) - \mathrm{min}(z_{i}), \mathrm{max}(w_{i}) - \mathrm{min}(w_{i}))$ を出力する

計算量は $O(N)$

供養

Difficulty: 1226 (記事作成時点)

任意の $i, j$ について、$i \rightarrow j$ の移動コストを $c_{i, j}$ としたとき、任意の $i, j, k$ について $c_{i, j} + c_{j, k} \ge c_{i, k}$ が成立する
よって、すべての都市を1度ずつ通って都市 $1$ に戻る最短コストを探す
都市集合 $V$ の任意の部分集合 $S$ を通過済で、現時点で都市 $u$ にいる場合の最短コストを $\mathit{DP}_{S, u}$ とすると、 $\mathit{DP}_{S, u} = \underset{v \in S \setminus u}{\mathrm{min}}(\mathit{DP}_{S \setminus u, v} + c_{v, u})$ と計算できる

実装は

$0 \le i, j \lt N$ について $C_{i, j} = |X_{j} - X_{i}| + |Y_{j} - Y_{i}| + \mathrm{max}(0, Z_{j} - Z_{i})$ を計算する
$2^{N} \times N$ の配列 $\mathit{DP}$ を作成し、$\mathit{DP}_{i, j} = \infty$ で初期化する
$\mathit{DP}_{1, 0} = 0$ とする
$0 \le S \lt 2^{N}$ について、以下の処理を実施する
- $0 \le u \lt N$ について、以下の処理を実施する
  - $S \& 2^{u} = 0$ ならば何もしない
  - $0 \le v \lt N$ について、$\mathit{DP}_{S, u} = \mathrm{min}(\mathit{DP}_{S \text{^} u, v} + C_{v, u}, \mathit{DP}_{S, u})$ を計算する
長さ $N$ の配列 $L$ を用意し、$L_{i} = \mathit{DP}_{S, i} + C_{i, 0}$ とする
$\mathrm{min}(L_{i})$ を出力する

計算量は $O(2^{N}N^{2})$