ABC307_D – Mismatched Parentheses

問題

D - Mismatched Parentheses

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44811027 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解けた

以前解けなかった問題だったが、比較的簡単に解けた。

以下、解法を書く。
$)$がでたら$($まで遡って削除する。
$($がなかったら削除はしない。

遡って削除する際は、単純に後ろから検索して最初の$($を探索する。
計算量の最大は全ての文字が消されるパターンなので$N$の2倍程度の計算量になる。