CODE THANKS FESTIVAL 2014 A : H - 模様替え

本番は部分点どまり。
http://code-thanks-festival-2014-a-open.contest.atcoder.jp/tasks/code_thanks_festival_14_quala_h

問題

R*Cのグリッド状に区切られた長方形の布がある。
y行目x列の各セルには色S[y][x]が塗られている。

ここから、長方形領域を切り出したとき、高さ・幅が２以上かつ色合いが点対称となるような切り出し方は何通りあるか。

解法

部分点1解法

長方形領域を全パターン列挙し、点対称判定を行うとO(R^3*C^3)かかる。
R,C≦20ならこれで間に合う。

部分点2解法

点対称判定を高速化することを考える。
以下のすべてを満たせば、(x,y)-(x+dx,y+dy)の長方形は点対称である。

• (x+1,y)-(x+dx-1,y+dy)が点対称
• (x,y+1)-(x+dx,y+dy-1)が点対称
• (x,y)と(x+dx,y+dy)の色が同じ
• (x,y+dy)と(x+dx,y)の色が同じ

長方形領域の全パターン列挙を小さい順に行うことで、上記判定はO(1)で行える。
これで計算量は長方形領域の全パターン列挙のみO(R^2*C^2)となる。
R,C≦100ならこれで間に合う。

満点解法

O(R^2*C^2)だけど何とか間に合うパターン。

まず長方形の左端Lと右端Rの対を総当たりする。
次に、点対称の中心となる行yを総当たりで選択する。
後は(y-i)行目のL～Rマス目と、(y-i)行目のL～Rマス目を左右反転させたものが一致する限りiをインクリメントさせていくことができ、答えの候補とすることができる。
L～Rマスの一致判定はローリングハッシュによりO(1)で行える。

他の人もO(R^2*C^2)だけど、ループ順などの取り方で数倍性能が変わるようだ。

struct RollingHash {
	static const ll mul0=10009,mul1=10007;
	static const ll add0=1000010007, add1=1003333331;
	string s; int l;
	ll hash_[300],pmo_[300];
	void init(string s) {
		this->s=s; l=s.size(); int i,j;
		hash_[0]=0; pmo_[0]=1;
		FOR(i,l) pmo_[i+1]=pmo_[i]*mul0;
		FOR(i,l) hash_[i+1]=(hash_[i]*mul0+add0+s[i]);
	}
	ll hash(int l,int r) { // s[l..r]
		return hash_[r+1]-hash_[l]*pmo_[r+1-l];
	}
};

int R,C;
string S[2][300];
ll ret;
RollingHash rh[2][260];


void solve() {
	int i,j,k,l,r,x,y; string s;
	int x1,x2,y1,y2,mx,my;
	cin>>R>>C;
	
	FOR(y,R) {
		cin>>S[0][y];
		S[1][y]=S[0][y];
		reverse(S[1][y].begin(),S[1][y].end());
		rh[0][y].init(S[0][y]);
		rh[1][y].init(S[1][y]);
	}
	
	FOR(x1,C) for(x2=x1+1;x2<C;x2++) {
		FOR(y,R) {
			int t=y,b=y+1; //even
			while(t>=0 && b<R && rh[0][t].hash(x1,x2)==rh[1][b].hash(C-1-x2,C-1-x1)) ret++,t--,b++;
			t=b=y; // odd
			while(t>=0 && b<R && rh[0][t].hash(x1,x2)==rh[1][b].hash(C-1-x2,C-1-x1)) ret+=(t!=y),t--,b++;
		}
	}
	cout<<ret<<endl;
}

まとめ

いい機会なのでローリングハッシュをライブラリにしておいた。