Codeforces #707 Div1 : D. Tiles for Bathroom

割と力技感のある問題。
https://codeforces.com/contest/1500/problem/D

問題

N*Nのグリッドがあり、それぞれ整数値が書かれている。
また、入力値として正整数Qが与えられる。

グリッド内のあるk*kの正方形区間内において、ユニークな値がQ個以下のものを数え上げることを考える。
k=1～Nのそれぞれにおいて、上述の値を求めよ。

解法

Qが小さい点に注意。
以下の3つの配列を考える。
R(r,c) := (r,c)の右側にあるユニークな値の登場位置を、近い順にQ個覚えておく
D(r,c) := (r,c)の下にあるユニークな値の登場位置を、近い順にQ個覚えておく
X(r,c) := (r,c)の右下にあるユニークな値の登場位置を、近い順にQ個覚えておく

R(r,c),D(r,c),X(r,c)のうち、(r,c)に近いQ個まで探索すれば、(r,c)を左上とした区間のうち、値がQ個以下となる最大サイズがわかる。

(r,c)を大きい順に処理し、R(r,c)からR(r,c-1)、D(r,c)からD(r-1,c)、X(r,c)からX(r-1,c-1)の差分を更新しつつ、上記値を求めて行くとO(N^2*Q)で解ける。

int N,Q;
int C[1515][1515];
int A[1515][1515];
int ret[1515];
vector<pair<int,int>> R[1515][1515],D[1515][1515],X[1515][1515];
int cnt[1515*1515];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(y,N) FOR(x,N) scanf("%d",&C[y][x]);
	for(y=N-1;y>=0;y--) {
		for(x=N-1;x>=0;x--) {
			vector<pair<int,int>>& RR=R[y][x];
			vector<pair<int,int>>& DD=D[y][x];
			vector<pair<int,int>>& XX=X[y+1][x+1];
			vector<pair<int,int>> V;
			swap(RR,R[y][x+1]);
			swap(DD,D[y+1][x]);
			
			FOR(i,RR.size()) if(C[RR[i].first][RR[i].second]==C[y][x]) {
				RR.erase(RR.begin()+i);
				break;
			}
			RR.insert(RR.begin(),{y,x});
			if(RR.size()>Q+1) RR.resize(Q+1);
			FOR(i,DD.size()) if(C[DD[i].first][DD[i].second]==C[y][x]) {
				DD.erase(DD.begin()+i);
				break;
			}
			DD.insert(DD.begin(),{y,x});
			if(DD.size()>Q+1) DD.resize(Q+1);
			
			
			int a=0,b=0,c=0;
			while(a<RR.size()||b<DD.size()||c<XX.size()) {
				if(V.size()==Q+1) break;
				int da=(a==RR.size())?5000:max(RR[a].first-y,RR[a].second-x);
				int db=(b==DD.size())?5000:max(DD[b].first-y,DD[b].second-x);
				int dc=(c==XX.size())?5000:max(XX[c].first-y,XX[c].second-x);
				if(da<=min(db,dc)) {
					if(cnt[C[RR[a].first][RR[a].second]]==0) {
						V.push_back(RR[a]);
						cnt[C[RR[a].first][RR[a].second]]++;
					}
					a++;
				}
				else if(db<=min(da,dc)) {
					if(cnt[C[DD[b].first][DD[b].second]]==0) {
						V.push_back(DD[b]);
						cnt[C[DD[b].first][DD[b].second]]++;
					}
					b++;
				}
				else {
					if(cnt[C[XX[c].first][XX[c].second]]==0) {
						V.push_back(XX[c]);
						cnt[C[XX[c].first][XX[c].second]]++;
					}
					c++;
				}
			}
			X[y+1][x+1].clear();
			FORR(v,V) {
				cnt[C[v.first][v.second]]--;
				assert(cnt[C[v.first][v.second]]==0);
			}
			
			
			if(V.size()>=Q+1) {
				V.resize(Q+1);
				r=max(V.back().first-y,V.back().second-x);
				r=min({r,N-y,N-x});
			}
			else {
				r=min(N-y,N-x);
			}
			ret[r]++;
			X[y][x]=V;
			
		}
	}
	
	for(i=N;i>=1;i--) ret[i]+=ret[i+1];
	for(i=1;i<=N;i++) cout<<ret[i]<<endl;
	
}

まとめ

なんとなくCodeforcesらしい問題。