codeFlyer 2018 final C - 部分文字列と括弧

• 問題

問題概要

'(' と ')' のみからなる文字列Sがある.
1 <=i < j <=|S| で, S[i :j] が対応が取れているのは何組あるか.
1 <= |S| <= 10⁵

思考と反省

• 考えたこと 構文木作れば k 個の子を持つ親を見つける度に kC2 足していけば出来る -> 再帰で実装しよう
  -> (k+1)C2 - kC2 = k なのでその高さに戻ってくる度にもともと持ってた子を足していけば良さげ

• 詰まったこと kC2を足していく方針にすると,再帰で実装するとき根がない時困った .. 例えば ()() -> ダミーでSを(S)にするかと思ったけどヤバそうなのでやめた
  -> 差分とってkだったので,戻ってくる度にそれまで見た子を足していく方針でOKだった -> 結果的にけんちょんさんのブログと全く同じだったけど,こっちの方がとても明快

普通に)で毎回returnしていくと )( みたいな文字列でめっちゃ困る
-> 意味をなさない ) は分けなきゃいけなかった

結局よくあるstackの +1/-1 で考えるべきだった.
このstack上で,どういうクエリになるかを一番先に考える.
-> その発想で考えると,この問題だと安直なRMQで解けた

メモ

逆ポーランド記法っぽい問題,発想はすぐ出るけど実装詰まるから困る

コード