[Codeforces] Hello 2019 C. Yuhao and a Parenthesis

Yuhao and a Parenthesis

括弧列の典型的な問題だと思います。

考え方

題意

与えた得られた括弧列の配列に対して、括弧の対応が取れるように二組の括弧列を連結させます。このとき、括弧の対応が取れたペアの数の最大値を求めます。

方針

括弧列の対応の問題でAtCoderに類題があります。

https://abc064.contest.atcoder.jp/tasks/abc064_d

解説は下のサイトから。

https://www.hamayanhamayan.com/entry/2017/06/10/224823

どのようなとき、括弧列の対応が取れるかを考えると、既に括弧の対応が取れている括弧列を連結させるとペアが一組できます。ここで、ある括弧列を S とします。

括弧の対応が取れる括弧列は、S を先頭から調べていき、” ( ” が現れたら \( + 1\) ” ) ” が現れたら \( -1 \) とカウントします。このカウントが途中で負の値を取らず、最終的なカウントの値が \( 0 \) であるとき、対応がとれています。

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

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

コード

感想

括弧列の問題を以前解いたことがあったので、なんとか正解することができました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする