TopCoder SRM 688 (Div. 2) Medium. ParenthesesDiv2Medium

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

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

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

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