天下一プログラマーコンテスト2014 決勝 : B - 天体位置観測

これ想定解なんかな。
http://tenka1-2014-final-open.contest.atcoder.jp/tasks/tenka1_2014_final_b

問題

N個の星の座標と、M種類の星座が与えられる。

各星座は、L[i]個の星の座標で与えられる。
全体の位置を平行移動したものも元の星座とみなすが、拡大縮小や回転はできない。

N個の星の中に、各星座となる星群が何組登場するか答えよ。

解法

各星座について、適当に1個代表を定める。
例えば以下のコードでは、最も左端で、かつ左端の星が複数あるなら一番上を代表とみなす。

N個の各星の位置に代表の星を持ってきたとき、星座中の他の星の位置にちゃんと星があるかチェックすればよい。
ただ、この処理だと全体でO(NML)かかりTLEする。

幸い、星座を構成する星は10x10の範囲内に収まっている。
よってN個の各星について、周囲の星をbitmap表現したものを持っておくことで、星の存在チェックをbitwise andを使い高速化できる。

int N,M,L;
set<int> SS[1000200];
pair<int,int> P[100200],S[200];
int mask[100200][21],mask2[20];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>P[i].first>>P[i].second;
	FOR(i,N) SS[P[i].second].insert(P[i].first);
	sort(P,P+N);
	FOR(i,N) {
		for(y=-9;y<=9;y++) {
			FOR(x,10) mask[i][10+y] |= (SS[P[i].second+y].find(P[i].first+x)!=SS[P[i].second+y].end())<<x;
		}
	}
	
	while(M--) {
		cin>>L;
		FOR(i,L) cin>>S[i].first>>S[i].second;
		sort(S,S+L);
		for(i=L-1;i>=0;i--) S[i].first-=S[0].first;
		int mix=99999999,miy=99999999;
		FOR(i,L) mix=min(mix,S[i].first),miy=min(miy,S[i].second);
		ZERO(mask2); 
		FOR(i,L) mask2[S[i].second-miy] |= 1<<(S[i].first-mix);
		
		int ret=0;
		FOR(i,N) {
			int ok=1;
			FOR(y,10) if((mask[i][10-(S[0].second-miy)+y] & mask2[y])!=mask2[y]) ok=0;
			ret+=ok;
		}
		
		cout<<ret<<endl;
	}
}

まとめ

こんな定数倍高速化っぽい方法でいいのかな…？