https://codeforces.com/contest/1095/problem/E
'('と')'からなる括弧列が与えられる。この括弧列を1箇所変更して対応のとれた括弧列にできる場合、そのような場所の数を出力せよ。
はじめに、')'が'('より多い場合には括弧列を反転（reverseして'('と')'を入れ替え）すれば、常に'('が多いものとして扱うことができる。以下、そのように扱う。
括弧列を変更する際、必ず'('を')'に変更することになる。よって、初期状態で'('が')'よりちょうど2つだけ多い括弧列以外は対応の取れた括弧列に変えることはできない。
'('を+1, ')'を-1と考えて累積和をとると、途中で累積和が負になる場所がなければ対応の取れた括弧列であることがわかる。'('を')'に変更すると、変更した箇所以降の累積和は2減るので、1箇所変更して累積和が負になる部分が存在しなくなるかどうかを高速に判定するためには、0文字目から$i$文字目までの間で累積和が負である場所の数を数えた配列と、$i$文字目から最後までの間で累積和が1以下であるような場所の数を数えた配列を持っておけばよくて、ある場所で'('を')'に変更したときに対応の取れた括弧列であるかどうかを判定するためには、その場所より前に累積和が負になる場所がなく、その場所より後ろに累積和が1以下になる場所がなく、かつその場所での累積和が2以上であればよい。これをすべての場所について判定すれば、この問題が解ける。
コンテスト中にそれっぽい考察はできていたが、最後まで詰めきれなかった。