ABC167 - F - Bracket Sequencing - Senの競技プログラミング備忘録

概要

N個の文字列S[i]が与えられる。それぞれのS[i]は'(' or ')'で構成されている。これらの{S}を好きな順番でつなげ合わせた時、正しいかっこ列を作ることができるのだろうか？できるならYes、できないのならNo。

制約： 1 <= N <= 10^6, 各S[i]の長さはたかだか10^6以下である。

考えたこと

1. ~~コドフォで見たことあるな~~制約からして適宜な基準にソートして貪欲がありそうだと見当をつける。
2. 各S[i]のかっこ列を2つの数字、「後ろにつなげるのに最低必要なnestの深さ」と「最終的なnestの増減」に抽象化する。
3. これらを並べ替えるとき、証明を慎重にしながら貪欲法アルゴリズムを見つけて、それを考える。

考察

まず、nestの深さをかっこ列のある時点で正当になるに必要な')'の個数とする。
次に、かっこ列の生成、並び替えではかっこ列を「後ろにつなげるのに最低必要なnestの深さ」と「最終的なnestの増減」に抽象化するのは典型パートである。無駄なかっこ列をそぎ落とすと、すべてのかっこ列は「)*(*」の形になる。(s*はsを非負の整数個という意味)

よって、各かっこ列の「後ろにつなげるのに最低必要なnestの深さ」をneed, 「最終的なnestの増減」をdeltaと表すとする。この(need, delta)の組をもとに適宜なつなげる順番を定めれば貪欲法の完成である。なお、((()のような、後ろにつなげるのに必要なnestの深さが必要ではない場合は、need==0としておく。

まず、すべての大本として、全文字列のdeltaの和は0でなければならない。ならなければ、(の数と)の数は一致しないということになる。

次に、delta>=0の(need, delta)とそうでないdeltaに分ける。これは、できるだけかっこ列のnestを深くした(するためにdeltaが正、ゼロのものをすべて集める)のちに、かっこ列のnestが減っていく(deltaが負のかっこ列たち)部分をつなげていくということになる。明らかにこれが最善である。(かっこ列のnestが深ければ深いほど、全体的なデータセットに対して、正しいかっこ列が作れる範囲？が広義単調増加するから)

さて、ここでまずdelta >= 0のかっこ列(上り坂)をどのようにつなぎ合わせれば一番よいのだろうか？
答えは、needが低い方からつなげるである。(同じneedの間ではどの順序でもよい)
なぜならば、delta>=0であるため、つなげればつなげるほどneedの制約が広義増加的に緩和されていく。ゆえに、needの制約が低い順でつなげればよく、逆にそれが最適なつなげ方である。(これでneedにnestの深さが届かない場合は、そもそもどうつなげても不可能)

では、delta < 0(下り坂)の場合はどうなるのだろうか？
同じような感覚で、needが高い順からつなげる。(同じneed間ではどの順序でもよい)
しかし、これは嘘解法である。(反例思いつかないぐらい精巧ではあるがちゃんと落とされる)

本当の解法を考えるには、次のようにする。
下りていくのではなく、山の反対側から登るというイメージで、deltaが負のかっこ列たちのneedやdeltaを新しく言い換えたNEED、DELTAを考える。

f:id:Sen_comp:20200810182906j:plain