Codeforces #166 Div2. D. Good Substrings

さてDiv2 D、この位になると少し難しくなる。
http://codeforces.com/contest/271/problem/D

問題

各アルファベットに、良し悪しが与えられる。
文字列が与えられたとき、その部分文字列のうち悪い文字がK個以下のものの数を答える。

解法

文字列長L=1500なので、部分文字列候補は高々L^2=2.25M通り位。
部分文字列における悪い文字の数は、事前に文字の途中までの悪い文字累積数を数えておくと定数時間で求められるので、2.25M通りのループは時間的には問題ない。

ただ、ここで問題となるのは、同一の部分文字列は二重カウントしないこと。
つまり、前と同じ部分文字列が出たのが２度目か覚えておかないといけない。
これをSTLのsetで行うと、MLEを起こした。
そのため、部分文字列を文字列長とハッシュ値で分類し、先頭位置の数値を個別のvectorに入れることで同値判定の範囲を狭めたところ、検索も速くなってメモリ消費量も減った。

char str[1600];
int bad[1600];
char bi[30];
int N,K,LL;
int ncount[1600][1600];
vector<int> ssl[1600][10];

void solve() {
	int x,y,i,j,res,TM,nc,l,nb;
	ll o,p;
	
	GETs(str);
	GETs(bi);
	K=GETi();
	N=strlen(str);
	FOR(i,N) bad[i]=1-(bi[str[i]-'a']-'0');
	
	FOR(x,N) {
		int nb=0;
		int hash=0;
		for(l=1;x+l<=N;l++) {
			nb+=bad[x+l-1];
			if(nb>K) break;
			hash+=str[x+l-1];
			
			int mat=0;
			FOR(y,ssl[l][hash%10].size()) {
				int tx=ssl[l][hash%10][y];
				if(strncmp(str+tx,str+x,l)==0) {
					mat=1;
					break;
				}
			}
			if(mat==0) ssl[l][hash%10].push_back(x);
		}
	}
	int nu=0;
	FOR(l,16000) nu+=ssl[l/10][l%10].size();
	_P("%d\n",nu);
	
	return;
}

まとめ

setやmapにstringを放り込むのはメモリ消費が怖いね。
Pretestが強力なCodeforcesだから良かったけど、TopCoderなら本番で一発アウトだな…。