ARC 085 D - ABS

• 問題
• AC

想定解は${\mathcal O}(1)$らしいけれど、それはそれとして自分がDPの計算量を理解できていないことがわかった。

$b_0 = Z, b_1 = W, b_2 = a_1, ..., b_{N+1} = a_N$と添え字を付け替えた上で、$f(i, j)$をXが$i$枚目、Yが$j$枚目まで取った状況からの最終スコアとする。求めたいのは$f(0, 1)$で、漸化式は

$f(i, j) = \begin{cases} | b_i - b_j | & (i = N+1 \ \text{or} \ j = N+1)\\ \max(f(j+1, j), ..., f(N+1, j)) & (i < j) \\ \min(f(i, i+1), ..., f(i, N+1)) & (i > j) \\ \end{cases}$

と書ける。状態数が$N^2$だからメモ化で余裕……となんとなく思ってしまってそのまま書いたらTLEした。実際には、それぞれの$f(i, j)$を求める際に$N+1-\min(i, j)$ 回の参照が発生するので、この漸化式のままでは全体の計算量が${\mathcal O}(N^3)$になる。

$i<j \ (i>j)$のとき$i=0, ..., j-1 \ (j=0, ..., i-1)$のいずれであっても答えが変わらないことを利用して、
$f(i, j) = \begin{cases} | b_i - b_j | & (i = N+1 \ \text{or} \ j = N+1)\\ f(0, j) & (0 < i \le j-1) \\ \max(f(j+1, j), ..., f(N+1, j)) & (i = 0) \\ f(i, 0) & (0 < j \le i-1) \\ \min(f(i, i+1), ..., f(i, N+1)) & (j = 0) \\ \end{cases}$
とすれば${\mathcal O}(N^2)$になる。めでたしめでたし。

空間計算量と時間計算量を混同してはいけないという当然の話であった。