C - 部分文字列と括弧
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
(
と )
からなる文字列 S が与えられます。次の条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組はいくつあるでしょうか。
条件: - S の i 文字目から j 文字目まで (両端を含む) を取り出した時、その文字列は括弧の対応が取れている。
括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。
- 空文字列
- ある括弧の対応が取れている文字列 A, B が存在し、 A, B をこの順に連結した文字列
- ある括弧の対応が取れている文字列 A が存在し、
(
, A,)
をこの順に連結した文字列
制約
- 1 ≤ |S| ≤ 10^5
- S は
(
,)
のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組の個数を出力せよ。
入力例 1
((())
出力例 1
2
- S の 2 文字目から 5 文字目までを取り出すと、
(())
です。これは括弧の対応が取れています。 - S の 3 文字目から 4 文字目までを取り出すと、
()
です。これは括弧の対応が取れています。
よって、 (2, 5) および (3, 4) が条件を満たします。
入力例 2
(()()(())(
出力例 2
7