kmjp's blog

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

yukicoder : No.866 レベルKの正方形

まんまと想定誤解法にはまってしまった。
https://yukicoder.me/problems/no/866

問題

N*Nのグリッドが与えられる。
各セルには文字が書かれている。

このうち正方形の区間において、矩形内の登場文字種別がK通りなものは何通りか。

解法

まず各文字の登場回数について累積和を求めておき、矩形内の登場の有無をO(1)で判定できるようにしておく。

あとは矩形の左上を総当たりしながら、条件を満たす右下の範囲を求めよう。
1つの方法としては、「K通り以上になる最小の矩形のサイズ」「K通り以下になる最大の矩形のサイズ」をそれぞれ2分探索する方法があるが、微妙にTLEする。
そこで尺取り法を行おう。
一つ左上のマスを矩形範囲の左上とする場合の結果から初めて行けばよい。

前処理と尺取り法いずれも文字種別をcとしてO(N^2*c)で済む。

int H,W,K;
string S[2020];
int C[2020][2020][26];
int PL[2020][2020];
int PR[2020][2020];

int num(int y,int x,int s) {
	int num=0,i;
	FOR(i,26) if(C[y+s][x+s][i]-C[y][x+s][i]-C[y+s][x][i]+C[y][x][i]>0) {
		num++;
		if(num>K) return num;
		if(num+(26-i)<K) return num;
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) {
			FOR(i,26) {
				C[y+1][x+1][i]=C[y][x+1][i]+C[y+1][x][i]-C[y][x][i];
				if(S[y][x]=='a'+i) C[y+1][x+1][i]++;
			}
		}
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) {
		int L=0,R=0;
		if(y&&x) {
			L=max(0,PL[y-1][x-1]-1);
			R=max(0,PR[y-1][x-1]-1);
		}
		
		while(y+L+1<=H&&x+L+1<=W&&num(y,x,L+1)<K) L++;
		while(y+R+1<=H&&x+R+1<=W&&num(y,x,R+1)<=K) R++;
		PL[y][x]=L;
		PR[y][x]=R;
		ret+=R-L;
	}
	cout<<ret<<endl;
}

まとめ

最初まんまと二分探索に走ってタイムロスした。