pekempeyのブログ

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

TopCoder SRM 688 (Div. 1) Easy. ParenthesesDiv1Easy

問題概要

括弧列が与えられる。ある区間を反転させ、さらに括弧の種類をトグルするという操作を 10 回まで行うことができる。対応のとれた括弧列に変える方法を示せ。

解法

(), ()(), (()) などを反転させればわかると思うが、元々対応している括弧は操作によって対応が崩れることはない。そのため対応している () を除外してもよい。

() を除外してみると ))))))))))))(((((((((((( のような列になる。これであれば簡単に解ける。

TopCoder SRM 688 (Div. 1) Easy. ParenthesesDiv1Eas ...

解法を聞けばなるほどと思う問題。((((( みたいなケースが危険?