Codeforces #215 Div1. B. Sereja ans Anagrams

本番割とすんなり解けたと思ったらTLEだった。
ホントもったいない…。
http://codeforces.com/contest/367/problem/B

問題

N要素の整数列A[i]、M要素の整数列B[i]、自然数Pが与えられる。
ここで、ある数qのうち、以下を満たすものを列挙せよ。

• 0<=q、q+(M-1)*P
• A[q]、A[q+P]、A[q+2*P]、…、A[q+(M-1)*P]のM要素で構成する数列を並べ替えるとBと一致する。

解法

ある数qについてA[q]、A[q+P]、A[q+2*P]、…、A[q+(M-1)*P]に登場する各数の個数がわかっているとする。
そこからA[q+P]、A[q+2*P]、…、A[q+(M-1)*P]、A[q+M*P]に登場する各数の個数は、A[q]とA[q+M*P]の分だけ考慮すればよいのでO(1)で求まる。

よって、各0<=q

ll N,M,P;
int A[200010],B[200010];

void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>N>>M>>P;
	FOR(i,N) cin>>A[i];
	FOR(i,M) cin>>B[i];
	set<int> Q;
	
	map<int,int> MM,MM2;
	FOR(j,M) MM2[B[j]]--;
	FOR(i,P) {
		if(i+(M-1)*P>=N) continue;
		MM=MM2;
		for(j=i;j<N;j+=P) {
			MM[A[j]]++;
			if(MM[A[j]]==0) MM.erase(A[j]);
			if(j-M*P>=0) {
				MM[A[j-M*P]]--;
				if(MM[A[j-M*P]]==0) MM.erase(A[j-M*P]);
			}
			if(MM.empty()) Q.insert(1+j-(M-1)*P);
		}
	}
	
	_P("%d\n",Q.size());
	ITR(it,Q) _P("%d ",*it);
	_P("\n");
}

まとめ

TLEには気を付けましょう。