Codeforces #390 Div2 E. Dasha and cyclic table

こういうのはECRでいいんじゃ…。
http://codeforces.com/contest/754/problem/E

問題

N*Mの２次元グリッドがある。
各セルにはアルファベット小文字が格納されている。

それとは別に、R*Cの２次元グリッドがある。
各セルはアルファベットまたは"?"が格納されている。

後者のグリッドの左上マスを前者の(x,y)に合うように動かす。
前者のグリッドをリピートしたものに、後者のグリッドがマッチするか(より正確に言えば、前者のマス((i+x)%N,(j+x)%M)が後者の(i,j)にマッチする)かどうかを各(x,y)に対し求めよ。

解法

愚直に全探索するとO(NMRC)かかる。
このままだとTLが厳しいが、bitsetを使いビット演算に落とし込めばO(NMRC/wordsize)となんとか間に合う。

前者のグリッドについて、セル数分のbitを持つbitsetを26個作ろう。
各bitは、セルの文字に対応するbitsetにおいてのみセットされる。

後者のグリッドのセル(i,j)の文字が"?"以外であれば、その文字に対応するbitsetを座標(-i,-j)分ずれるようrotateしてbitwise-orをとっていけばよい。

int H,W;
int TH,TW;
string S[404];
string T[404];

bitset<170000> B[26];
bitset<170000> R,R2,mask,lef[401],ri[401];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			B[S[y][x]-'a'][y*W+x]=1;
			R[y*W+x]=1;
		}
	}
	lef[0]=R2=R;
	for(x=1;x<=W;x++) {
		lef[x]=lef[x-1];
		FOR(y,H) lef[x][y*W+W-x]=0;
		ri[x]=(~lef[x]) & R;
	}
	
	mask=~R;
	
	cin>>TH>>TW;
	FOR(y,TH) {
		cin>>T[y];
		FOR(x,TW) if(T[y][x]!='?') {
			r=T[y][x]-'a';
			int yy=y%H;
			int xx=x%W;
			// up y
			bitset<170000> BT=((B[r]>>(yy*W)) | (B[r]<<(W*H-(yy*W))))&R2;
			// left x
			R &= ((BT>>(xx))&lef[xx]) | ((BT<<(W-xx))&ri[xx]);
		}
	}
	
	FOR(y,H) {
		FOR(x,W) _P("%d",R[y*W+x]==1);
		_P("\n");
	}
}

まとめ

FFTとか思いつかない…。