Codeforces Round #594 (Div. 1) B. The World Is Just a Programming Task (Hard Version)

Problem - B - Codeforces

問題概要

長さ $n$ の括弧列 $S$ が与えられる。長さ $n$ の括弧列のスコアを、「 $S$ を $k$ 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす $k (0\le k \lt n)$ の個数とする。

$S$ に対して1度だけ、2箇所を選んでスワップする操作を行うことが出来る（同じ位置を選んでもよい）。操作後の $S$ の最大スコアと、そのスコアを実現するスワップ位置の1例を求めよ。

制約

$1 \le n \le 300000$

解法

巡回シフトが正しい括弧列になる条件

正しい括弧列の問題では ( を $+1$ 、) を $-1$ とした累積和を考えるのが定石です。この値が全て非負でありかつ最後に0になることが、文字列が正しい括弧列である必要十分条件です。

与えられた文字列について、以下のように $\pm 1$ に変換した数列 $\lbrace a_{i}\rbrace$ とその累積和の列 $\lbrace C_{i} \rbrace$ を求めます。

f:id:betrue12:20191020234126p:plain

まず $C_{n} = 0$ であることは大前提です。そうでない場合、シフトやスワップをどうやってもスコアは絶対に0なので適当なスワップ位置を答えて終了します。

巡回シフト後の文字列が正しい括弧列になっている必要十分条件は、 $C_{i}$ の中で最も値が小さい位置が左端になるようにシフトすることです。つまり $C_{i}$ が最小値を取るような $i$ の個数がそのままスコアになります。

このとき $C_{0}$ と $C_{n}$ は同じシフトに対応するのでダブって数えてはいけません。以降は $C_{1}, ..., C_{n}$ を数える対象として扱います。

スワップが累積和に与える影響

次にスワップの影響を考えます。同じ文字同士をスワップした場合は当然何の変化もありません。異なる文字をスワップした場合には、

左側にある $+1$ と右側にある $-1$ をスワップすると、その間にある $C_{i}$ が $-2$ される。
左側にある $-1$ と右側にある $+1$ をスワップすると、その間にある $C_{i}$ が $+2$ される。

という変化があります。

スワップ後の累積和を $C_{i}^{\prime}$ と表記します。 $C_{i}$ の最小値を $m$ とすると、 $C_{i}^{\prime}$ の最小値は $m-2$ 以上 $m+2$ 以下の範囲に存在することが分かります。

最小値とスワップの正負を決め打ってDP

最小値の候補は5個で、スワップによって $-2$ されるか $+2$ されるかは2通りです。これらを決め打って全部試します。

スワップ後の最小値として決めた値を $t$ とします。このとき、 $t$ より小さい $C_{i}^{\prime}$ があってはならず、 $t$ に等しい $C_{i}^{\prime}$ の個数がスコアになります。

また、左側にある $+1$ と右側にある $-1$ をスワップすると仮定します。このときこの2要素の間にある累積和については $C_{i}^{\prime} = C_{i}-2$ となります。

このとき $C_{i}^{\prime}$ は、左から順に

ゾーン0： $C_{i}^{\prime} = C_{i}$ である。
ゾーン1： $C_{i}^{\prime} = C_{i} - 2$ である。
ゾーン2： $C_{i}^{\prime} = C_{i}$ である。

という3つのゾーンに分かれます。

f:id:betrue12:20191021000822p:plain

このゾーンに基づいてDPを定義します。つまり

$dp\lbrack i \rbrack\lbrack j \rbrack =$ 累積和 $C_{i}^{\prime}$ まで見て、 $C_{i}^{\prime}$ はゾーン $j$ に属していて、 $t$ より小さい $C_{i}^{\prime}$ はこれまで存在していないときの、 $t$ に等しいこれまでの $C_{i}^{\prime}$ の個数（スコア）の最大値

というDPを考えることができます。

$dp\lbrack i \rbrack\lbrack j \rbrack$ からの遷移を考えます。まず同じゾーンへの遷移があります。それに加えて今は左側にある $+1$ と右側にある $-1$ をスワップすると仮定しているので、 $a_{i} = +1$ であるときにはゾーン0→1の遷移、 $a_{i} = -1$ であるときにはゾーン1→2の遷移が起こり得ます。

遷移後のゾーンを $k$ とします。遷移後の累積和 $C_{i+1}^{\prime}$ の値は、元の $C_{i+1}$ に遷移後の所属ゾーン $k$ に応じた変化量を足したものです。これが $t$ より小さい場合は遷移を却下します。ちょうど $t$ である場合はスコアを1増やして、そうでない場合にはスコアそのままで、 $dp\lbrack i+1 \rbrack\lbrack k \rbrack$ に遷移します。

最後まで遷移すると、 $dp\lbrack n \rbrack \lbrack 0 \rbrack$ には「スワップしなかった場合の最大スコア」、 $dp\lbrack n \rbrack \lbrack 2 \rbrack$ には「スワップした場合の最大スコア」が入っています。前者を採用する場合は適当に同じ位置をスワップしたことにします。後者を採用する場合はDPの復元を行ってスワップ位置を特定します。