ARC 073 F - Many Moves

• 問題
• AC

クエリ$x_i$を処理した際に、動かさなかったほうのコマが位置$y$にある場合の最短時間を$dp[i][y]$とせよ。この時、コマは位置$x_i$と$y$にある。ここからクエリ$x_{i+1}$を処理するとき、コマを$x_i$→$x_{i+1}$と移動させ、$y$のコマを動かさないなら

$dp[i+1][y] = dp[i][y] + |x_{i} - x_{i+1}| \qquad (1)$

$y$→$x_{i+1}$と移動させ、$x_{i}$のコマを動かさないなら

$dp[i+1][x_i] = \min_y (dp[i][y] + |y - x_{i+1}|) \qquad (2)$

これで計算できる形になっているので、初期化を$dp[1][B] := |x_1 - A|, dp[1][A] := |x_1-B|$、それ以外は$+\infty$としてDPすれば答えは求まる。ただ、このままでは間に合わないので遷移を工夫する必要がある。

$(2)$の右辺は、次のように絶対値を外して書ける:

$dp[i+1][x_i] := \min \begin{cases} \min_{y \ge x_{i+1}} (dp[i][y]+y)-x_{i+1} \\ \min_{y < x_{i+1}} (dp[i][y]-y)+x_{i+1}\end{cases}$

それぞれの$\min$はたぶんセグメント木等で得られる形になっているので、$dp$を1次元のセグメント木にして${\mathcal O}(\log N)$で遷移できそう。具体的には、

$T := \min \begin{cases} \min_{y \ge x_{i+1}} (dp[y]+y)-x_{i+1} \\ \min_{y < x_{i+1}} (dp[y]-y)+x_{i+1}\end{cases} \qquad (3)$

を求めたあと、$dp$全体に$|x_i - x_{i+1}|$を加算し、最後に$dp[x_i] := T$と更新し直せばよい。

悩んだのは$(3)$の計算をどう実現するかで、テクニックを知らなかったのでもっとも直接的な扱い方をした:

セグメント木の元を$((y^+, d^+), (y^-, d^-))$と４値で持ち、演算を

$((y^+_1, d^+_1), (y^-_1, d^-_1)) \oplus ((y^+_2, d^+_2), (y^-_2, d^-_2)) \\ = ((y^+_1, d^+_1)と(y^+_2, d^+_2)のうちy^+_1+d^+_1, y^+_2+d^+_2の小さいほう,\\ \qquad (y^-_1, d^-_1)と(y^-_2, d^-_2)のうちy^-_1-d^-_1, y^-_2-d^-_2の小さいほう)$

で定める。値$\Delta$の区間加算は
$((y^+, d^+), (y^-, d^-)) \mapsto ((y^+ +\Delta, d^+), (y^- + \Delta, d^-))$

でよい。

これでACできたが、素朴すぎて定数倍がかなり重かった。¹

skyさんの解説にもっとスマートな方法が載っていた。最初から$dpl [y] := dp[y] + N - y, dpr[y] := dp[y] +y$みたいに補正したものを用意すればよいらしい。なるほど……

---

1. そもそもコンパイル時間だけで700ms消費している。 ↩︎