DDPC 2016 本選 問題Cの補足
計算量がよくわからないとか言ってましたが、実はらしいです。
というのも、長さの括弧列に対する計算量をとすると、
(1)
(2)
となるはずです(は正の定数)。
仮にとしてみましょう。
(1)
となるためには、であればよいです。
(2)
となるためには、であればよいです。
よって、のときが成立します。
逆に、のような入力では明らかになので、
となります。
前回、(2)のほうが計算量的に重たいとか言ってましたが、
実は(1)も(2)も(長さの増え方を考えると)同じくらいの計算量なんですね。
ちなみに、僕の解法はいわゆる木DPと同等らしく、
一見だけど実は、というのは有名な話らしいです。
参考 : 二乗の木 DP - (iwi) { 反省します - TopCoder部