codeFlyer （bitFlyer Programming Contest）：C - 部分文字列と括弧
問題
解法
'(' を +1，')' を -1 として累積和 imos を取った時，当てはまる (i, j) の組は
imos[i] == imos[j] - 1
imos[k] >= imos[j] - 1 (i <= k <= j)
を満たしていればよい．１つ目の条件にあてはまる (i, j) の組を std::map などを使って列挙し，それらが２つ目の条件に当てはまるかどうか RMQ のセグ木を使って調べればよい．全ての考えられる組について後者の処理をしていると O(|S|^2) となり間に合わないので，自明に２つ目の条件が当てはまる場合は枝刈りをする．O(|S|)．
解答
２つ目の条件を考えていなくて 2 WA，枝刈りが出来ていなくて 2 TLE してしまった．自明なケースの枝刈りも重要だと感じた．
