Codeforces #815 : Div2 E. Misha and Paintings

これまた本番の正答率の割にupsolve数が多い問題。
https://codeforces.com/contest/1720/problem/E

問題

N*Nの行列が与えられる。
ここから、有る正方形領域を選択してある1つの値で上書きすることを繰り返し、行列中にちょうどK種類の値が登場するようにしたい。
最小何回処理をすればよいか。

解法

元々登場する値がK種類以下の場合、1回の処理で1種類増やせるので、K種類になるまでそれを繰り返せばよい。
元々K種類より多くの値が登場する場合、じつは解は2以下である。

とすると、あとは解が1かどうかを総当たりで判定すればよい。
尺取り法の要領で、正方形領域をずらしながら判定していこう。

int N,K;
int A[505][505];
int C[505*505];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	int num=0;
	FOR(y,N) FOR(x,N) {
		cin>>A[y][x];
		if(C[A[y][x]]++==0) num++;
	}
	if(num<=K) {
		cout<<K-num<<endl;
		return;
	}
	int sy,sx;
	FOR(sy,N) FOR(sx,N) if(sy==0||sx==0) {
		ZERO(C);
		num=0;
		FOR(y,N) FOR(x,N) {
			if(C[A[y][x]]==0) num++;
			C[A[y][x]]++;
		}
		int len=0;
		for(int cy=sy,cx=sx;cy<N&&cx<N;cy++,cx++) {
			while(cy+len<N&&cx+len<N&&num>K) {
				for(y=cy;y<=cy+len;y++) {
					if(--C[A[y][cx+len]]==0) num--;
				}
				for(x=cx;x<cx+len;x++) {
					if(--C[A[cy+len][x]]==0) num--;
				}
				len++;
			}
			if((num==K&&len!=N)||num==K-1) {
				cout<<1<<endl;
				return;
			}
			for(y=cy;y<=cy+len;y++) if(C[A[y][cx]]++==0) num++;
			for(x=cx+1;x<=cx+len;x++) if(C[A[cy][x]]++==0) num++;
			len--;
		}
		
	}
	cout<<2<<endl;
	
}

まとめ

解が2以下って気づけるかどうか次第な気がする。