DDCC2020本戦 C - 特別講演「括弧列と塗り分け」

問題
提出コード

解法

という区間の塗り分け方、みたいなものを考えたいですが、上手いこと工夫しなければ計算量が大きくなってしまいそうです。
ここで、括弧列が木に対応することを思い出すと、二乗の木DPができそうになってきます。

• 番目の文字(開き括弧)とそれに対応する閉じ括弧までの区間で、となるような塗り方

を考えます。
子にあたる部分についての上記の値が求まっていると、それらを組み合わせてとなるような塗り方は簡単に計算ができます。
なので、再帰をしていって、子から計算をしていけばよいです。
このDPは、まさに二乗の木DPの形をしているので、計算量的にも問題ありません。
が答えです。