selpo's diary

主に競プロの解説をします。C#erです。

DDPC 2016 本選 問題Cの補足

計算量がよくわからないとか言ってましたが、実はO(|S|^2)らしいです。

というのも、長さ2xの括弧列に対する計算量をf(x)とすると、
(1)f(x+1)=f(x)+ax
(2)f(x+y)=f(x)+f(y)+bxy
となるはずです(a,bは正の定数)。

仮にf(x)\leq Cx^2としてみましょう。

(1)f(x+1)\leq Cx^2+ax\leq C(x+1)^2
となるためには、2C\geq aであればよいです。
(2)f(x+y)\leq Cx^2+Cy^2+bxy\leq C(x+y)^2
となるためには、2C\geq bであればよいです。

よって、C=\max(a,b)/2のときf(x)\leq Cx^2が成立します。
逆に、(((\cdots)))のような入力では明らかにO(x^2)なので、
f(x)=\Theta(x^2)となります。

前回、(2)のほうが計算量的に重たいとか言ってましたが、
実は(1)も(2)も(長さの増え方を考えると)同じくらいの計算量なんですね。

ちなみに、僕の解法はいわゆる木DPと同等らしく、
一見O(N^3)だけど実はO(N^2)、というのは有名な話らしいです。
参考 : 二乗の木 DP - (iwi) { 反省します - TopCoder部