Google Code Jam 2013 Round 1C : A. Consonants

さてR1C。GCJのRound1は段々簡単になるイメージがあったけど、そうでもなかった。
今回はそうでもなかった。
幸いBは知ってる問題だったので、本番出てもAL・BL・CSは取れたな。
https://code.google.com/codejam/contest/2437488/dashboard#s=p0

問題

L文字(L<=10^6)のアルファベット小文字からなる文字列と、数値Nが与えられる。
文字列から生成可能な部分文字列のうち、子音がN個以上連続しているものの数を答える。

解法

まずは文字列中の母音と子音を0と1を置き換える。

真っ先に思いつくのは、全部の部分文字列を生成してチェックすることだけど、部分文字列がO(L^2)通りでチェックにO(L)かかるので、合計でO(L^3)かかる。
L<=100のSmallならこれで良いけどLargeは無理。

次に、部分文字列の先頭を固定して、末尾を伸ばしていき、途中でN個以上連続の子音を通過した数を数えていくと、O(L^2)だけどまだLargeは無理。
ただ、この考え方からわかるのは、ある文字列の始点に対して、末尾を１文字ずつ伸ばしていったとき、最初にN個連続の子音を通過すると、残り末尾を伸ばした文字列はすべてN個連続の子音を通過する
こと。

この事実を利用すると、尺取り法を用いてO(L)で処理できる。
先頭から１文字ずつ見て、P文字目でN個以上連続子音が続いた場合、そこから(N文字以上)左側にある文字Qを始点とする文字列は、(P-Q)文字目までは条件を満たさず、P文字目～L文字目は条件を満たすので、Qを始点とする(L-P+1)種類の部分文字列ができる。
上記処理を文字列全体に適用すればよい。

int N;
int L;
char str[1000003];
int CL[1000003];
//           abcdefghijklmnopqrstuvwxyz 
char mp[27]="01110111011111011111011111";

void solve(int _loop) {
	int i,j,x,y,ne=0;
	
	GETs(str);
	L=strlen(str);
	N=GETi();
	
	x=y=0;
	FOR(i,L) {
		CL[i]=L;
		if(mp[str[i]-'a']) y++;
		else y=0;
		if(y>=N) while(x<=i-(N-1)) CL[x++]=i;
	}
	ll res=0;
	FOR(i,L) res += L-CL[i];
	
	_PE("Case #%d: %lld\n",_loop,res);
}

まとめ

一瞬文字列の長さに戸惑ったけど、冷静に対応すれば簡単だった。