2019年2月7日木曜日

ARC 085 D - ABS

ARC 085 D - ABS

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

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

f(i,j)={bibj(i=N+1 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) 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}

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

i<j (i>j)i<j \ (i>j)のときi=0,...,j1 (j=0,...,i1)i=0, ..., j-1 \ (j=0, ..., i-1)のいずれであっても答えが変わらないことを利用して、
f(i,j)={bibj(i=N+1 or j=N+1)f(0,j)(0<ij1)max(f(j+1,j),...,f(N+1,j))(i=0)f(i,0)(0<ji1)min(f(i,i+1),...,f(i,N+1))(j=0) 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}
とすればO(N2){\mathcal O}(N^2)になる。めでたしめでたし。

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