codeFlyer （bitFlyer Programming Contest）オープンコンテスト : C - 部分文字列と括弧

問題

C - 部分文字列と括弧

( と ) で構成される文字列 S の中で括弧の対応が取れている部分文字列の数を求める問題。

解法

まず、括弧が対応している最小の部分文字列を列挙したい。S の最初から ( なら +1 、) なら -1 という基準で累積和的なものを取っておく（i文字目までの和を imos_i とする）。imos_i - 1 == imos_j となる (i, j) の組が最小の部分文字列になるので、これを lower_bound() を使って全て求める。ここで、std::vector<std::pair<LL, LL>> の中で std::lower_bound() を使うと TLE し、std::set<std::pair<LL, LL>> の中で set.lower_bound() を使うと AC した（非常に謎）vector.erase() が O(N) かかってしまうため TLE した（ @rian_tkb さん、ご指摘ありがとうございました）。

std::vector<std::pair<LL, LL>> を使った方のコード，lower_bound がやばいというより vector の erase に O(N) かかっていて O(N^2) になっていると思います

— りあん (@rian_tkb) 2018年7月18日

最小の部分文字列が全て列挙できたので、あとは配列を使ってそれらがいくつそれぞれ連続するか求めながら答えを出していけばよい。

解答

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

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

std::string S;
LL ans;

int main()
{
	in >> S;
	std::vectorimos(S.length(), 0), mark(S.length() + 1, -1), res(S.length() + 1, 0);
	std::set<std::pair<LL, LL>>list;
	rep(i, S.length())
	{
		imos[i] = (S[i] == '(' ? 1 : -1);
		if (i > 0) imos[i] += imos[i - 1];
		list.insert(std::make_pair(imos[i], i));
	}
	rep(i, S.length())
	{
		if (imos[i] == -1 || S[i] == ')') continue;
		auto endP = list.lower_bound(std::make_pair(imos[i] - 1, i + 1));
		if ((*endP).first == imos[i] - 1 && (*endP).second > i)
		{
			mark[i] = (*endP).second;
			imos[(*endP).second] = -1;
			list.erase(endP);
		}
		auto beginP = list.find(std::make_pair(imos[i], (LL)i));
		list.erase(beginP);
		imos[i] = -1;
	}
	rep(i, S.length())
	{
		if (mark[i] != -1)
		{
			++res[i];
			if (mark[mark[i] + 1] != -1) res[mark[i] + 1] += res[i];
		}
		ans += res[i];
	}
	out << ans << std::endl;
	return 0;
}