E - Most Valuable Parentheses Editorial
by 
Yukkku
この解説では末尾に0個以上の)を加えることで正しい括弧列にできるような括弧列を「前正しい括弧列」と呼ぶことにします.
言い換えると, 任意の接頭辞で(の個数が)の個数以上になるような括弧列を前正しい括弧列と呼びます.
この問題は以下のような貪欲法で解くことができます.
- 括弧列を\(s=\)
(((\(...\)(((で初期化する - \((1, 2, ..., 2N)\)の順列\(P = (P_1, P_2, ..., P_{2N})\)を\(A_{P_1}, A_{P_2}, ..., A_{P_{2N}}\)が広義単調増加になるようにとる
- \(i\)を\(1\)から\(2N\)まで1つづつ変化させながら以下を繰り返す
- \(s\)の\(P_i\)文字目を
)に置き換えたものを\(t\)とし, \(t\)が前正しい括弧列なら\(s\)を\(t\)で置き換える.
- \(s\)の\(P_i\)文字目を
- この時点での\(s\)が最大のスコアを取れるような括弧列になっている.
正当性の証明
前正しい括弧列について, 以下の事が成り立ちます (証明略)
- 括弧列\(s\)について, \(s\)が前正しい括弧列でかつ\(s\)が含む
(の個数と)の個数が等しいとき, かつそのときに限り\(s\)は正しい括弧列である - 前正しい括弧列の任意の接頭辞は前正しい括弧列である
- 前正しい括弧列の0個以上の
)を(に置き換えても前正しい括弧列である
最終的な\(s\)が正しい括弧列になる証明
初期状態(((\(...\)(((は前正しい括弧列で, ループ中では\(t\)が前正しい括弧列であるときだけ\(s\)を\(t\)で置き換えているので, \(s\)は常に前正しい括弧列であることが保たれます.
最終的な\(s\)が正しい括弧列でないと仮定します. 前正しい括弧列の定義から\(s\)の末尾に0個以上)を足せば\(s\)は正しい括弧列になり(以下これを\(s'\)と呼ぶことにします), 正しい括弧列ではないという仮定から, \(s\)に加えられた)の数は0個ではないです. 更に, 正しい括弧列は偶数文字で, \(s\)自体も偶数文字なため, 加えられた)の数が1個でもおかしく, 2個以上になるとわかります.
前正しい括弧列で(を含まないものは空文字列しか存在せず, \(s\)は空文字列でないため, \(s\)は少なくとも1つの(を持ちます. その中で一番最後の(の位置を探し, その位置を\(k\)と置きます. すると
- \(s[k]\)が最後の
(であったことと末尾に2個以上)を足したことから\(s'[k+1]=\))になるとわかる - \(s'[k, k+1]=\)
()になることがわかり, 正しい括弧列の定義から, この部分列を取り除いても\(s'\)は正しい括弧列のままである - この時点の\(s'\)は「長さ\(2N+2\)以上括弧列から\(2\)字取り除いたもの」なので長さが\(2N\)以上で, 長さ\(2N\)の接頭辞\(s''\)を持つ
- \(s'\)は正しい括弧列であったため前正しい括弧列でもあり, \(s''\)はその接頭辞なので前正しい括弧列である
- \(s''\)は操作の内容から\(s[k]\)だけが
)に置き換わったものである
というように, \(s[k]\)を)に置き換えても前正しい括弧列に保たれることがわかります.
\(P\)は順列なので\(P_i = k\)となる\(i\)をループ中で通っているはずです. その時点の\(s\)は操作を逆から見ると「最終的な\(s\)の0個以上の)を(に置き換えたもの」になっています. 同様に, その時点の\(t\)も「『最終的な\(s\)の\(s[k]\)を)に置き換えたもの』の0個以上の)を(に置き換えたもの」になっています.
「最終的な\(s\)の\(s[k]\)を)に置き換えたもの」は前正しい括弧列であると先程示したので, \(t\)も前正しい括弧列であるということになり, これは最終的な\(s[k]=\)(であることと矛盾します.
よって背理法により最終的な\(s\)は正しい括弧列になります.
スコアが最大になる証明
順列\(Q = (Q_1, Q_2, ..., Q_{2N})\)を\(Q_{P_i} = i\)となるように定めます. \(A_i < A_j\)なら\(Q_i < Q_j\)になり, ループで調べられた順, と見ることができます.
何らかの正しい括弧列\(u\)が\(s\)と等しくないとします. \(i\)を「\(s[i]=\))かつ\(u[i]=\)(な\(i\)の中で\(Q_i\)が最小なもの」とします. \(u\)が\(s\)と異なることから条件を満たす\(i\)は常に存在します.
\(s[j]=\)(かつ\(u[j]=\))を満たす\(j\)について,「\(Q_k>Q_j\)となる全ての\(k\)について\(s[k]\)を(で置き換え, 更に\(s[j]\)を)に置き換えたもの」を\(t\)とすると, これは\(Q_j\)回目のループでの\(t\)と一致し, \(s[j]=\)(であることから\(t\)は前正しい括弧列ではありません.
\(Q_j < Q_i\)と仮定すると\(i\)の定義から\(t\)は「\(u\)の0個以上の)を(に置き換えたもの」になり, 前正しい括弧列の性質と矛盾するため, \(Q_j > Q_i\)です.
前述のような条件をみたす\(j\)を1つ選び, \(u\)の\(u[i]\)を)に, \(u[j]\)を(に置き換えたものを\(u'\)とします.
\(u'\)が正しい括弧列だった場合
スコアを減少させずに\(u\)から\(s\)により近い(ハミング距離が小さい)正しい括弧列\(u'\)を作ることができました.
\(u'\)が正しい括弧列でなかった場合
正しい括弧列の性質から, このとき常に\(i\) < \(j\)です. \(u'\)の(の数と)の数は等しいため, \(u'\)は前正しい括弧列でもありません. 前正しい括弧列の「任意の接頭辞で(の個数が)の個数以上になる」を踏まえると\(k < j\)の範囲に\(s[k]=\)(, \(u[k]=\))を満たすような(\(j\)に課した制約と同じです)\(k\)が存在すると言えます.
この\(k\)で\(u'\)を作るところからやり直せば\(u\)から\(s\)により近い(ハミング距離が小さい)正しい括弧列を作ることができます. 作り直すと\(j\)は減少するので, 必ず有限回のやり直しで\(u'\)が正しい括弧列になります.
全体で, このような操作を繰り返すことでスコアを減少させること無く任意の正しい括弧列を\(s\)にすることが可能とわかり, \(s\)でスコア最大が達成されます.
ループ中で愚直に前正しい括弧列か判定すると1回あたり\(\Theta(N)\)かかり, 全体で\(\Theta(N^2)\)かかってしまい, 間に合いません. この判定を高速に行う方法を考えます.
括弧列\(s\)について, 数列\(B_s = (B_{s, 1}, B_{s, 2}, ..., B_{s, 2N})\)を\(B_{s, i}=\)「\(s\)の先頭から\(i\)文字の中で(であるものの個数」\(-\)「\(s\)の先頭から\(i\)文字の中で)であるものの個数」と定義すると, \(s\)が前正しい括弧列であることは\(\min(B_{s, 1}, B_{s, 2}, ..., B_{s, 2N})\ge 0\)と言い換えられます.
括弧列\(s\)の(を)に置き換えたとき, 置き換えた位置を\(i\)とすると\(B_{s, i}, B_{s, i+1}, ..., B_{s, 2N}\)が\(2\)ずつ減ります. つまり, この数列\(B_s\)について
- 指定した位置から末尾まで値を\(2\)ずつ増やす/減らす
- 全体の最小値を調べる
が高速に行えれば前正しい括弧列の判定ができます. 遅延Fenwick木や遅延Segment木などを用いればこれらの操作が\(O(\log N)\)で行えるため, 全体で\(O(N\log N)\)でこの問題を解けました.
posted:
last update: