Bracket Sequencing - abc 167 f
#かっこ列 #kyopro_friends さん #貪欲法
開いてる ")" が少ない文字列から左から埋めた方がいいか?
開いてる ")" というのは, 相手の "(" がいない ")"
ある時点で, "(" の数より ")" の数が多くなってはダメだから
それの相手の "(" が手前にいないとかっこ列にならない
次の方法で分析する
開いてる ")" の数は, 始め 0 として, "(" が来たら +1, ")" が来たら -1 する
折れ線グラフで, ペアになってるかっこの部分を引っこ抜く
上図の, 囲ったオレンジの部分
ペアになってるとこを全て引っこ抜くと谷になる
山があれば, ペアが残ってる
そして, その谷の下がってる部分が開いてる ")" の数
実は, 一番小さいところの数字である
上図の上から, -3, -2, 0
閉じてる ")" は, 相方の "(" による +1 を -1 する
かっこ列の条件は,
1. "(" と ")" の数が等しいこと,
2. すべての ")" に相方がいること
上の表現方法でいうと,
1. 最後の数字が 0 であること
2. 途中で負にならないこと
1. は文字列の順番に関係ない
開いてる ")" の数は 2. に関係するか?
開いてる ")" の数が小さい順に文字列を並べるのであった
すなわち, 最下点の数字が大きい順に並べる
では, 最下点の数字が同じ場合はどうするか
一番右端の数字が大きいほど, 次の文字列以降負の数が出にくい
スタート地点が高くなるから
さて, 一番右端の数字より最下点の数字を優先させていいか
下のテストケース 1 を見る
一番右端の数字より最下点の数字を優先して失敗する例
どうすべきか具体例で考えよう
2 つを比較する
最下点が -2 で右端が 5 の文字列 1 と, 最下点が -1 で右端が -1 の文字列 2 はどっちを先にすべきか
-2 するのが許されていて, -3 するのが許されていない状況にしよう
文字列 1 を先にすると, 高さが +5 になり, もちろん文字列 2 を置ける
文字列 2 を先にすると, 高さが -1 されて, 文字列 2 は置けない
高さが計 -1 - 2 = -3 になるところが出る
-2 すら許されていないとする
文字列 1 は先に置けない
文字列 2 を先においても, 文字列 1 は置けない
一般的に考える
最下点が 0 以上で右端も 0 以上の場合
問答無用で先に並べていい
最下点が負で右端が 0 以上の場合
この文字列を置くことで最下点が負になってしまうとする
残りの 2 つの場合の文字列を先においても, スタート地点の高さは減ってしまうので結局無理
よって, この場合の文字列の中で, 並びを考える
スタート地点 - 最下点 が負にならないのであれば, どの順番でもいい
なぜなら, 途中で負にならないのであれば, 結局高さが右端の値だけ大きくなるので, 足せるなら足す
+1 + 2 も +2 + 1 も変わらない
実は, 上 2 つの場合をまとめると, 右端の値が 0 以上であるなら, 最下点の数字が大きい順である
先に最下点が小さいのを置くくらいなら, 最下点が大きいのを置くことができて, スタート地点の数字を大きくできる
今まで左から文字列をつなげてきたが, 残り 2 つの場合は, 右から文字列をつなげれば, 上 2 つの場合と同じようにできる
左からつなげるなら, 最下点が小さい順
ソースコード
https://atcoder.jp/contests/abc167/submissions/13186315
テストケース
5
4
(((
)))((
))(
)
2
)(
)(
3
)
(
)))(((
4
))(
)(
)
((
5
)))((
)((
(
)(
)
Yes
No
No
Yes
No
