kmjp's blog

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

CSAcademy Round #46 : D. Count Gigel Matrices

なんかよくわからないけど1位だった。
https://csacademy.com/contest/round-46/task/cntgigelmat/

問題

01で構成されたグリッドがある。
このグリッドないの部分正方形において、周辺部および左上から右下にかけての対角線が1で埋まっているものの数を求めよ。
周辺および対角線以外の部分は0/1どちらでも良い。

解法

まず各マスが大きさいくつの正方形の左上および右下点になりうるかを求めよう。
マス(y,x)に対しそれぞれの最大値をRD(y,x)、LU(y,x)とする。
RD(y,x)は各マスから右・下・右下向きのうち1が連続する数の最小値となる。
LU(y,x)も同様に左・上・左上向きの連続する1の数を数えていこう。

求める形状は正方形なので、左上と右下は同じ斜めのライン*1程度で求めることができる。

int H,W;
int A[2020][2020];
int L[2020][2020],R[2020][2020];
int U[2020][2020],D[2020][2020];
int DL[2020][2020],DR[2020][2020];
int B[2020][2020],C[2020][2020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	V add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};

ll tot;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>s;
		FOR(x,W) A[y][x]=s[x]=='1';
	}
	
	FOR(y,H) FOR(x,W) if(A[y][x]) {
		L[y][x]=1+(x?L[y][x-1]:0);
		U[y][x]=1+(y?U[y-1][x]:0);
		DL[y][x]=1+((y&&x)?DL[y-1][x-1]:0);
		B[y][x]=min({L[y][x],U[y][x],DL[y][x]});
	}
	for(y=H-1;y>=0;y--) for(x=W-1;x>=0;x--) if(A[y][x]) {
		R[y][x]=1+R[y][x+1];
		D[y][x]=1+D[y+1][x];
		DR[y][x]=1+DR[y+1][x+1];
		C[y][x]=min({R[y][x],D[y][x],DR[y][x]});
	}
	
	for(i=-H-W;i<W;i++) {
		BIT<int,13> bt;
		ZERO(bt.bit);
		vector<int> del[2020];
		FOR(y,H) {
			x=i+y;
			if(x<0||x>=W) continue;
			FORR(e,del[y]) bt.add(e+1,-1);
			if(A[y][x]) {
				bt.add(y+1,1);
				del[y+C[y][x]].push_back(y);
				tot+=bt(y+1)-bt(y+1-B[y][x]);
			}
		}
	}
	cout<<tot<<endl;
	
	
}

まとめ


シンプルな問題ながら割と手間取った。

*1:列-行)が一致するセル群が成すライン)上に存在する。 よってライン毎に左上と右下の点を数えていこう。 マス(y,x)に対し、右下の点となりうるのはd≦RD(y,x)かつLU(y+d,x+d)≧dとなる(y+d,x+d)である。 これはBITを使いO(NMlog(max(N,M