AtCoder Beginner Contest 167 F - Bracket Sequencing

F - Bracket Sequencing

解法

「正しい括弧列」について

この問題だと単に括弧列という言葉が使われていますが、どちらかと言うと「正しい括弧列」みたいな呼ばれ方をされることが多いです。

正しい括弧列の条件は、言葉で書くと

開き括弧と閉じ括弧の数が等しい。
それぞれの閉じ括弧について、それに対応する開き括弧がそれより前に出現している。

となりますが、これを ( を $+1$ 、) を $-1$ として見たときの先頭からの累積和で考えるのが定石です。すなわち上記の条件はそれぞれ累積和によって

全体の和がちょうど $0$ である。
先頭から累積和を取った時に、その最小値が $0$ 以上である。（つまり、先頭からどの地点までの累積和の値も負でない）

と書くことができて、これらを両方を満たすことが正しい括弧列であることの必要十分条件です。

f:id:betrue12:20200511080152p:plain

パーツを繋げられる条件を考える

与えられた「パーツ」である $S_{i}$ それぞれについて、累積和の最小値 $m_{i}$ と全体の和 $s_{i}$ を求めます。パーツ $S_{i}$ はこの2つの値の組 $(m_{i}, s_{i})$ で特徴づけられます。

全てのパーツを連結した文字列が先ほどの条件を満たせるかどうかを考えます。まず条件1について、全体の和は繋げ方に依らず全てのパーツについての $s_{i}$ の和になります。なのでこれが $0$ であるかどうかを調べれば良いです。

条件2について考えます。パーツを前から順番に繋げて行って、それまでの累積和（つまりそれまでに使ったパーツの $s_{i}$ の和）が $T$ であるとします。初期状態では $T=0$ です。ここにパーツ $S_{x}$ をつなげると、

パーツ $S_{x}$ の中での、先頭からの累積和の最小値： $T + m_{x}$
パーツ $S_{x}$ 終了地点での、先頭からの累積和： $T + s_{x}$

となります。このとき $T+m_{x}$ が負になってしまうと条件2に違反するので、それまでの累積和が $T$ であるときにパーツ $S_{x}$ を付けられる条件は $T+m_{x} \ge 0$ と表現できます。そして累積和 $T$ は $T + s_{x}$ に変化します。

言い換えると $m_{x}$ は「大きいほどパーツ $S_{x}$ 自身を付けられる条件が緩くなる」、 $s_{x}$ は「大きいほどそれ以降のパーツを付けられる条件が緩くなる」ような値だと考えることができます。

f:id:betrue12:20200511081221p:plain

最適な連結順序を考える

以上の考察から、なるべく条件を満たせるようにするにはどのような順序でパーツを連結していけば良いかを考えます。

まず $s_{i} \ge 0$ であるパーツは、付ければ付けるほど $T$ が増加して条件を満たしやすくなるので、付けられるようになったものから付けてしまって良いです。よって付けられる条件が緩いもの、つまり $m_{i}$ が大きいものから順番に使うことにします。

それから $s_{i} \lt 0$ であるパーツを使っていきます。これは付けるほど後が厳しくなっていくので $m_{i}$ と $s_{i}$ の両方が絡んできます。「条件の厳しいものを早く消化したい」と思うと $m_{i}$ が小さいものから、「後の条件を厳しくしたくない」と思うと $s_{i}$ が大きいものから使いたくなります。

では結局どうすれば良いのかと言うと、 $s_{i} - m_{i}$ が大きいものから順番に使うのが最適になります。

証明1

実は過去に書いた記事に全く同じ証明があります。こちらを参照してください。場合分けが必要なのでちょっとややこしいです。

Codeforces Round #579 (Div. 3) F1. Complete the Projects (easy version) - ARMERIA

リンク先の記事における $(a_{i}, b_{i})$ を本解説の $(-m_{i}, s_{i})$ に置き換えてください。

証明2

対称性を利用します。

先ほどとは逆に、文字列末尾から見て ) を $+1$ 、( を $-1$ としたときの累積和を考えます。その最小値と全体の和を $m^{\prime}_{i}, s^{\prime}_{i}$ と書くことにします。

ここで $s^{\prime}_{i} = -s_{i}$ なので、 $s_{i} \lt 0$ であるパーツについては $s^{\prime}_{i} \gt 0$ です。そのため先ほど $s_{i} \ge 0$ であるパーツについて書いたことと同じように、これらのパーツは末尾から見て $m^{\prime}_{i}$ が大きいものから順番に使うとして良いです。

また図を見ると分かるように、末尾から見た累積和は先頭から見た累積和と比べて $s_{i}$ のぶんだけずれています。そのため $m^{\prime}_{i} = m_{i} - s_{i}$ が成り立ちます。よって末尾から見て $m_{i} - s_{i}$ が大きいものから、つまり先頭から見て $s_{i} - m_{i}$ が大きいものから順番に使うとして良いです。