AtCoder Grand Contest 048 B - Bracket Score

B - Bracket Score

解法

正しい括弧列の必要十分条件

いわゆる「正しい括弧列」の問題です。よく使われるアプローチとして累積和がありますが、今回は括弧が2種類あるので2つの累積和を管理する必要があり厳しそうです。

今回は別の性質を使うことにします。1種類の括弧 ( ) からなる括弧列が正しい括弧列であることの必要十分条件として、

文字列から連続する () を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する

ことが挙げられます。今回のように2種類の括弧列がある場合も、同様に

文字列から連続する () または [] を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する

ことが「良い括弧列」であることの必要十分条件になります。

AB文字列に置き換える

括弧列をそのまま考えるのは面倒なので、文字を2種類だけにします。括弧列 $s$ に対して、( と ) を A に、[ と ] を B に置き換えた文字列 $t$ を考えます。括弧列のスコアはこの $t$ から計算することができます。

もし $s$ が良い括弧列であるならば、先ほど確認した事実から、 $t$ は「文字列から連続する AA または BB を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する」という条件を必ず満たすはずです。逆に A または B からなる文字列 $t$ がそのような条件を満たすならば、操作列において取り除かれる AA を () に、BB を [] に置き換えることで必ず良い括弧列 $s$ を作ることができます。

このことから、括弧列ではなく A または B からなる文字列を最初から考え、「文字列から連続する AA または BB を取り除く操作を繰り返すことで、空文字列にできるような操作列が存在する」という条件のもとでスコアを最大化すれば良いことが分かります。

偶奇いずれかのインデックスを反転

ここまでの考察でも解けますが、もう1ステップ進んでみます。「連続する2文字を取り除く」という操作において、残された各文字が位置するインデックスの偶奇は変わりません。このことを利用して、初期状態で奇数インデックスに位置する文字だけ A と B を反転してみます。「連続する AA または BB を取り除く」という操作は、この反転によって「連続する AB または BA を取り除く」という操作に変わります。

そして連続する AB または BA を取り除く操作によって空文字列にできる必要十分条件は、A と B がちょうど同数存在することです。必要性は明らかで、十分性は「初期状態でA と B がちょうど同数であれば、操作の過程で A と B は常に同数であり、空文字列になるまで A と B が隣り合う箇所が常に存在する」ことから言えます。