読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

TopCoder SRM 688 (Div. 2) Medium. ParenthesesDiv2Medium

問題概要

長さ n の括弧列が与えられる。高々 (n+1)/2 回括弧の種類をトグルして、対応の取れた括弧列に変えて欲しい。

解法

元々対応している括弧を除外すると )))))((((( のような括弧列になる。これが分かれば後は )))))((((( を ()()()()() に変えればいい。これは (n+1)/2 回で収まる。

TopCoder SRM 688 (Div. 2) Medium. ParenthesesDiv2M ...


()()()()... になるようにトグルするという解法が見受けられた。これは )()()()( で落ちる。

対応の取れている括弧を除外するテク、割と汎用性が高そう。