kmjp's blog

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

Codeforces ECR #008 : E. Zbazi in Zeydabad

これ普通に1発正答してた。Dで無駄な時間を取っていなければ…。
http://codeforces.com/contest/628/problem/E

問題

N*Mのグリッドが与えられる。
うち一部のマスは埋まっている。

ある一連の正方形を成すマス群がZパターンであるとは、以下の条件をすべて満たす場合をいう。

  1. 正方形の上端に当たるマス群はすべて埋まっている。
  2. 正方形の下端に当たるマス群はすべて埋まっている。
  3. 正方形の左下角と右上角を結ぶ対角線上のマス群はすべて埋まっている。
  4. これら以外のマスの状態は問わない。

与えられたグリッドに、何個Zパターンがあるか答えよ。

解法

事前に各マスから左右方向と左下・右上方向に何個埋まったマスがあるか前処理をしておくと、正方形区間がZパターンかどうかはO(1)で求められる。
ただ、残念ながら正方形区間を愚直に列挙するとO(N*M*min(N,M))程度かかりTLEする。
そこで複数のZパターンをまとめて数え上げる必要がある。

例えば、右上マスを固定した場合、Zパターンを成す正方形を高速に数え上げることを考える。
右上マスから左側に何マス埋まったマスが続くか、また左下に何マス埋まったマスが続くかは、左記の前処理で高速に求められる。
上記2値(左側の埋まった連続マス数と左下側の埋まった連続マス数)の小さい方の値をaとすると、右上マスは1辺1~aのZパターンの右上マスになる可能性がある。
この範囲では、上記条件の1,3はすでに満たしている。後は1~aの正方形に対し、2を満たすか判定したい。

そこで平面走査を用いる。
左上から見て、(行+列)が一致するマス群に対し、平面走査をしよう。
右の列から順に平面走査を行い、「走査する列が該当するマスから右に連続した埋まったマスの右端に到達した」「走査する列該当マスを通り抜けた」タイミングを順に処理する。
BITを使い、各行において前者の処理を行ったのに後者の処理をまだ行ってない場合、その行はZパターンの下端となりうる。

int H,W;
string S[3030];

int R[3030][3030];
int L[3030][3030];
int C[3030][3030];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V total(int e) {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;}
	void clear() {ZERO(bit);};
};
BIT<int,14> bt;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) {
		for(x=W-1;x>=0;x--) if(S[y][x]=='z') R[y][x]=1+R[y][x+1];
		FOR(x,W) if(S[y][x]=='z') L[y][x]=(x)?(1+L[y][x-1]):1;
	}
	for(y=H-1;y>=0;y--) {
		FOR(x,W) if(S[y][x]=='z') C[y][x]=(x)?(1+C[y+1][x-1]):1;
	}
	
	ll ret=0;
	FOR(i,(H+W+3)) {
		vector<pair<int,pair<int,int> >> ev;
		FOR(y,H) {
			x=i-y;
			if(x<0 || x>=W) continue;
			if(S[y][x]=='.') continue;
			ev.push_back({-(x+R[y][x]-1),{0,y}});
			ev.push_back({-x,{1,y}});
			ev.push_back({-x,{2,y}});
		}
		sort(ALL(ev));
		bt.clear();
		FORR(r,ev) {
			y=r.second.second;
			x=i-y;
			if(r.second.first==0) bt.add(y+1,1);
			if(r.second.first==1) ret+=bt.total(y+min(L[y][x],C[y][x]))-bt.total(y);
			if(r.second.first==2) bt.add(y+1,-1);
		}
		
	}
	cout<<ret<<endl;
}

まとめ

これで自分で解いてて面白い解法だと思った。
Dが面倒で面白くなかったので、本番こっち解けばよかった…。