phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ABC167 F. Bracket Sequencing

問題

N個の「(」または「)」からなる文字列S_iが与えられる。
この文字列をすべて連結して括弧列を構成できるか判定せよ。

括弧列とは、

  • 空文字列
  • ある括弧列Aが存在して、「(」「A」「)」の順で連結した文字列
  • ある空でない括弧列A, Bが存在して、「A」「B」の順で連結した文字列

制約

  • 1 <= N <= 10^6
  • すべての文字列の長さの合計は10^6以下
  • S_iは空でない

解法

括弧列は、「(」を+1、「)」を-1として扱うと、

  • 合計が0になる
  • 途中で0未満にならない

をどちらも満たす。
よって、各文字列を「最大どこまでマイナスになるか?」と「最後はどこに位置するか?」で考えればよい。

大きなマイナスのある文字列があった場合、そのマイナス分で負にならないように最初にプラスを増やしておく必要がある。
なので、「最後はどこに位置するか?」がプラスになっているものを全部使って、できるだけ高い位置まで持っていきたい。
このとき、できるだけマイナスが少ないものから使っていけばよく、途中でマイナスになってしまう場合はNo。

全部使ってできるだけ高い位置まで来たら、今度は「最後はどこに位置するか?」がマイナスなものをうまく使って徐々に下っていきたい。

実は、逆方向から見てみると、終点位置から逆に上記と同様の方法で、負にならないよう同じ高さまで持っていけるか?を考えればよい。(線対称)

途中で負にならず、両側からたどった最終位置が同じ地点ならばvalidな括弧列が作れ、そうでなければ作れない。