DDCC 2016 本選 C - 特別講演「括弧列と塗り分け」

お題箱より。

解法

この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。

f:id:betrue12:20200817124335p:plain

それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張ります。これは森になりますが、一番外側に根と対応する見えない括弧があると思うと木になります。このようにすると、それぞれの括弧の中はその頂点以下の部分木と対応します。

まずはこの木をグラフとして作りましょう。 $S$ に含まれる括弧の組数を $N$ と置きます。根を頂点 $0$ とし、括弧に対して左括弧の登場順に頂点 $1, ..., N$ と番号を振ります。スタックを用意し、 $S$ を順番に見ていって左括弧があればスタックにその括弧の頂点番号を入れ、右括弧があればスタックから1つ取り出します。このスタックに入れた時に1つ前にある頂点番号が親です。

木を作ってしまえば、木DPができます。以下のように状態を定義します。

$sum\lbrack i\rbrack$ ：頂点 $i$ 以下の部分木に含まれる文字の数
$dp\lbrack i\rbrack\lbrack r\rbrack$ ：頂点 $i$ 以下の部分木に含まれる文字を塗る方法であって、条件に違反せず、赤の個数が $r$ 個であるような塗り方の数

頂点 $i$ について考える時には、まず初期条件をセットします。括弧 $i$ の塗り方 $4$ 通りを考えて、 $dp\lbrack i\rbrack\lbrack 0\rbrack = 1$ 、 $dp\lbrack i\rbrack\lbrack 1\rbrack = 2$ 、 $dp\lbrack i\rbrack\lbrack 2\rbrack = 1$ 、 $sum\lbrack i\rbrack = 2$ となります。ただし根については括弧がないので $dp\lbrack i\rbrack\lbrack 0\rbrack = 1$ 、 $sum\lbrack i\rbrack = 0$ です。

それから頂点 $i$ の子 $j$ それぞれについて、 $dp\lbrack j\rbrack$ を $dp\lbrack i\rbrack$ にマージしていきます。これは新しい $dp\lbrack i\rbrack$ 用の配列を用意して、組 $(r_{i}, r_{j})$ それぞれについて古い $dp\lbrack i\rbrack\lbrack r_{i}\rbrack$ と $dp\lbrack j\rbrack\lbrack r_{j}\rbrack$ の積を新しい $dp\lbrack i\rbrack\lbrack r_{i}+r_{j}\rbrack$ に加算していけば良いです。

このとき $r_{i}$ についてはその前までにマージ済みの $i$ 以下の部分木の頂点数、 $r_{j}$ については $sum\lbrack j\rbrack$ までしか見る必要はありません。これは通称「2乗の木DP」と呼ばれる計算量解析テクニックによって、全体 $O(N^{2})$ で動作します。

全ての子のマージが終わったら、「括弧 $i$ の内部に含まれる赤の個数 $r$ と青の個数 $b$ について $|r-b| \le K$ である」という条件に違反するものを排除します。赤の個数が $r$ であれば青の個数は $sum\lbrack i\rbrack - r$ なので、 $|2r-sum\lbrack i\rbrack| \gt K$ である $r$ について $dp\lbrack i\rbrack\lbrack r\rbrack = 0$ とすれば良いです。根についてはこの処理は行いません。