Codeforces #294 Div2 D. A and B and Interesting Substrings

今回はE以外実装が軽いね。
http://codeforces.com/contest/519/problem/D

問題

a～zの文字にそれぞれスコアが設定されている。
文字列Sが与えられる。
2文字以上のSの連続部分文字列のうち、先頭と末尾の文字が等しく、先頭と末尾を除いた文字の総スコアが0となる物の数を答えよ。

解法

先頭からp文字目までのスコアの合計をT(p)とする。
部分文字列S[x..y]のスコアはT(y)-T(x-1)となる。

このスコアを文字種別ごとにmap管理して数を数えていく。
以下のコードでは、M[先頭文字][合計スコア]=その条件を満たす先頭文字の数、を文字列の先頭から処理して加算している。

int X[30],L;
string S;
ll sum[101000];
map<ll,int> M[27];
ll ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,26) cin>>X[i];
	cin>>S;
	L=S.size();
	FOR(i,L) {
		ret += M[S[i]-'a'][sum[i]];
		sum[i+1]=sum[i]+X[S[i]-'a'];
		M[S[i]-'a'][sum[i+1]]++;
	}
	cout<<ret<<endl;
}

まとめ

ちょっと考えるけど、そのあとは実装が軽い問題。