kmjp's blog

競技プログラミング参加記です

Codeforces #524 Div2 E. Sonya and Matrix Beauty

最初手抜き実装したら案の定TLEした。
https://codeforces.com/contest/1080/problem/E

問題

H*Wの2次元のグリッド状に文字が配置されている。
このうち矩形部分に関し、以下の条件を満たすものはいくつあるか。

  • 同一行内で文字の入れ替えが任意にできる場合、各行および各列が回文であるようにできる。

解法

矩形部分の総当たりはO(H^2*W^2)なのでそれより短くしないといけない。
まず、列の範囲は愚直に総当たりすることにしよう。

列の範囲を定めたら、(行内の文字は入れ替え可能なので)各行において、各文字の登場回数を求めよう。
奇数回登場する文字が1個以下なら、その行は回文を生成できる。

あとは、この各行における各文字の登場回数に関する配列の列に対し、manacher法の要領で行方向において回文を生成する行の区間を数え上げよう。
文字種をcとしてO(W^2*H*c)で解ける。

int H,W;
int mask[251][251];
vector<int> V[256];
string S[256];

int hoge(int A,int B) {
	if(A>B) return 0;
	
	int L=B-A+1,i,j,k;
	vector<int> rad(2*L-1,0);
	for(i=j=0;i<2*L-1;i+=k,j=max(j-k,0)) {
		while(i-j>=0 && i+j+1<=2*L-1 && V[A+(i-j)/2]==V[A+(i+j+1)/2]) j++;
		rad[i]=j;
		for(k=1;i-k>=0 && rad[i]-k>=0 && rad[i-k]!=rad[i]-k; k++) rad[i+k]=min(rad[i-k],rad[i]-k);
	}
	int ret=0;
	FOR(i,2*L-1) {
		if(i%2) ret+=rad[i]/2;
		else ret+=(rad[i]+1)/2;
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			mask[y][x+1]=mask[y][x] ^ (1<<(S[y][x]-'a'));
		}
	}
	
	ll ret=0;
	FOR(x,W) {
		FOR(y,H) V[y]=vector<int>(26,0);
		for(l=1;x+l<=W;l++) {
			int pre=0;
			FOR(y,H) {
				ll r=mask[y][x+l]^mask[y][x];
				V[y][S[y][x+l-1]-'a']++;
				if(__builtin_popcount(r)>1) {
					ret+=hoge(pre,y-1);
					pre=y+1;
				}
			}
			ret+=hoge(pre,H-1);
			
		}
	}
	cout<<ret<<endl;
	
}

まとめ

manacher久々に見た。