[Codeforces] Hello 2019 C. Yuhao and a Parenthesis

2019年5月25日2020年1月20日

問題

Problem - C - Codeforces

Codeforces. Programming competitions and contests, programming community

https://codeforces.com/contest/1097/problem/C

方針

括弧列の対応

どのようなとき、括弧列の対応が取れるかを考えると、既に括弧の対応が取れている括弧列を連結させるとペアが一組できます。ここで、ある括弧列を S とします。括弧の対応が取れる括弧列は、S を先頭から調べていき、" ( " が現れたら \( + 1\) " ) " が現れたら \( -1 \) とカウントします。このカウントが途中で負の値を取らず、最終的なカウントの値が \( 0 \) であるとき、対応がとれています。

末尾までカウントし終えたとき、カウントの最小値が負の値であり、最終的なカウントの値が最小値と同じでない括弧列はどんな括弧列を連結させても、括弧の対応を取ることができません。例えば、" ) ) ( (" のような括弧列です。一方で、 " ) ) ( ( ) )" は " ( (" と対応を取ることができます。

括弧列の連結

カウントの最小値が負の値で、最終的なカウントの値が最小値と同じでない括弧列を取り除き、最終的なカウントの値の括弧列の個数を数えます。このとき、カウントの値が正と負の値で分け、絶対値が等しい括弧列がペアとなります。どのように連結させるかですが、カウントが正の括弧列を前に、負のものを後ろにして連結した括弧列は、途中で負の値を取らず、最終的なカウントの値が \( 0 \) となることが分かります。