codeFlyer （bitFlyer Programming Contest） C - 部分文字列と括弧 (500)

C - 部分文字列と括弧

概要

'('と')'からなる長さNの文字列Sがある。1 ≦ i < j ≦ Nなるi, jの組で、i文字目からj文字目までのSの部分文字列が「括弧の対応が取れている」ものはいくつあるか。

制約

1 ≦ N ≦ 10^5

方針

i文字目からj文字目までのSの部分文字列が括弧の対応が取れていることを確認するためには次のことが成り立てばよい。

• ポインタpを準備、p=0と初期化
• S[i]からS[j]を順にみてゆき、'('ならpを+1, ’)'ならpを-1する
• 最終的にp=0となり、かつ途中でpが負にならない

基本的にはすべての')'に対し、それより左にある'('について、上記の方法で括弧の対応が取れているものを数えればよい。ただし、これだと計算量O(N^2)で間に合わない。

①上記のpの累積和をとることを考える。すなわち、累積和の配列をAとすると、A[i+1] = A[i] + 1 if S[i] == '(' else A[i] - 1 としてAを計算する。このとき、上記条件は次のように言い換えられる。

• 最終的にp=0 ⇔ A[i] = A[j]+1
• 途中でpが負にならない ⇔ i ≦ k ≦ j なるkで、A[k] = A[j] - 1となるものがない

よって、S[i]を前から見ていき、S[j] = ')'なるjについて、A[k] = A[j] - 1となる最後のkより後のiについてA[i] = A[j] + 1 なるiの個数を数えればよい。

②さらに考察を進める。A[k] = A[j] - 1なるkが存在する場合、その時点でA[i] = A[j] +1なるiがいくつあるかのカウントをリセットすると考える。すると、これは定義域が[-N, N]である配列Bを保持し、次のような操作を考えればよい。

• p = 0, B[0] = 1からスタート (i≠0についてはB[i]=0)
• S[i] = '(' なら pを+1、B[p] = 1 と再初期化
• S[i] = ')' なら pを-1、B[p]をansに足し、B[p]を+1

S[i] = ')' でB[p]を足すとき、それ以前にB[p-1]になるようなことがあれば、その後の'('の時点でB[p]=1となっているので上記が達成できる。

感想

けんちょんさんのブログを参考にしました。
drken1215.hatenablog.com

①はO(NlogN)でできると思ったのですが、実装がうまくないせいかTLE
Submission #7202071 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

解答

Submission #7214856 - codeFlyer （bitFlyer Programming Contest）オープンコンテスト

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	string S;
	cin >> S;
 
	int n = S.size();
	ll ans = 0LL;
	vector<ll> B(220000, 0);
	int p = 110000;
	B[p] = 1;
	for(int i = 0; i < n; i++){
		if(S[i] == '('){
			p++;
			B[p] = 1LL;
		}else{
			p--;
			ans += B[p];
			B[p]++;
		}
	}
 
	cout << ans << endl;
}