WUPC 2019 : E - Artist

これはすんなりだったかな。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_e

問題

H*Wのグリッドが与えられる。各マス白黒のいずれかの値を持つ。
このグリッドにおいて、縦横に１本ずつ十字に切れ目を入れ、４つの矩形領域に分割することを考える。
その各領域を180度回転させ、また元のように連結させる。

各列・各行の黒マスの数が変化しない切れ目は何通りか。

解法

縦横独立に考えてよいことに着目しよう。
横線を入れる位置は、列方向の黒マスの数に影響しないし、縦線の位置は行方向の黒マスの位置に影響しない。
よって、条件を満たす横線と縦線の位置をそれぞれ求めて積をとればよい。

以下縦線を入れる位置について考える。
まず前処理として各列の黒マスの個数を求めて、その数からなる数列を考える。
この数列を分割したとき、前後それぞれが回文となれば条件を満たす。
そこで分割位置を総当たりしよう。回文判定はローリングハッシュでもよいが、定数倍の時間差が気になったので以下はZ-Algorithmで解いている。

int H,W;
vector<int> A[505050];
vector<int> R,C;

vector<int> Zalgo(vector<int> s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}


ll hoge(vector<int> V) {
	int N=V.size();
	vector<int> VR=V;
	reverse(ALL(VR));
	V.push_back(-1);
	VR.push_back(-1);
	int i;
	FOR(i,N) VR.push_back(V[i]);
	FOR(i,N) V.push_back(VR[i]);
	
	auto A=Zalgo(V);
	auto B=Zalgo(VR);
	
	int ok=0;
	for(int l=1;l<N;l++) {
		if(A[V.size()-l]==l && B[V.size()-(N-l)]==N-l) ok++;
	}
	
	return ok;
	
	
}

まとめ

ここらへんは順調でよかったね。