Serval and Parenthesis Sequence
問題はこちら 問題文難しくないですか...
自分が気づいたところ
括弧を扱う問題では，stackを用いると綺麗に書けるなと思い実装．しかしコンテスト時間内に問題文を解読できなかった...
解説を読んで
このブログとかが簡潔かつ分かりやすかった． perogram.hateblo.jp
使える(の数をカウントしておく(=cとする)．
?が現れたとき，c>0の場合貪欲に(を使う．なぜなら，なるべく(を左に持っていった方が途中で正しい数式になってしまう可能性が下がるから．c==0の場合は，(を使っても文字列全体として正しい数式になることはないので，)を使う．
そして，括弧の管理はstackで行う．s[i]=='('の時はstackにpush．s[i] == ')'の時は，stackが空でなければpop．といったようにする．stackが空になるということは，その時点で(と)の数が等しい．→正しい数式になっている．
これを踏まえると求められている条件は，「出力文字の途中でstackが空にならない．かつ，最後にはstackが空になる」であるので，それに従って貪欲に解を構成できるか試す．
https://codeforces.com/contest/1153/submission/52734359
自分の詰まったところ
- 問題文の解読．
- 変に左右の括弧の数を数えて累積和とかやってた．
- 不正解となり得るパターンをどのようにして判定するか．
学んだこと
- 片方を使える分だけ貪欲に使っていくと，もう片方とのマッチング可能性は下がっていく．
- stackを使わなくても,
( → +1,( → -1という風に変換してあげればもっと簡単に計算できる．
