AtCoder ARC #063 : F - すぬけ君の塗り絵 2 / Snuke's Coloring 2

これはしんどい。
http://arc063.contest.atcoder.jp/tasks/arc063_d

問題

2次元座標上で(0,0)-(W,H)を対角線とする軸に平行な矩形領域を考える。
この矩形領域中にN個の格子点(X[i],Y[i])がある。
これらの格子点は、X座標およびY座標ともに他の格子点とは一致しない。

各格子点に対し、以下のいずれかを行う

• x≦X[i]の領域を黒く塗りつぶす
• x≧X[i]の領域を黒く塗りつぶす
• y≦Y[i]の領域を黒く塗りつぶす
• y≧Y[i]の領域を黒く塗りつぶす

元の矩形領域のうち、塗りつぶされておらず残された矩形領域の周長が最大になるように塗りつぶし方を選択するとき、その周長を求めよ。

解法

全頂点左右を塗りつぶすまたは上下に塗りつぶすを選択すると、2*(max(W,H)+1)の周長は容易に得られる。
また、このような周長を得るには、残された矩形領域はx=W/2の直線かy=H/2の直線いずれかと交差しなければならない。

よって、以下x=W/2と交差する矩形領域のうちで周長を最大化する方法を考える。y=H/2もあとで同様に行えばよい。
初期状態では対象とするy座標を[0,H]の範囲で探索する。以下分割統治法の要領で探索対象を絞り込んでいく。

今y座標の区間[T,B]内のみで構成される矩形領域の最長周長を考える。
領域内の格子点が、y=Mを境に半々に分かれるとする。
(W/2,M)を矩形領域が含まないケースの周長は、[T,M]と[M,B]の矩形領域の周長を考えればよい。
その際含まれる格子点は半減していくので、計算量も半々になっていく。
残りは(W/2,M)を含む矩形領域を考える。

これはW/2の左側にある点について、初期状態ではその左側を塗りつぶすようにしておく。
以後、W/2に近い順に、(W/2,M)を含むよう上下に塗り分け方を変えたとき、周長がどうなるかを考えていけばよい。
今ある頂点(X[i],Y[i])の左側を塗りつぶしており、X[i]＜x＜W/2の間の格子点は(W/2,M)を含まないよう上下に塗り分けているとする。
そして塗られていないY座標の区間が[T',B']とする。
その際、尺取り法の要領で、x=W/2の右側にある格子点群に対し、どこまでは上下に塗り分け、どこからは右側を塗りつぶすかの境界を求めていけばよい。

int H,W,N;
int X[303030],Y[303030];
int ma;

void dfs(int T,int B,vector<pair<int,int>>& P) {
	if(T>=B || (B-T)+W<=ma) return;
	if(P.empty()) {
		ma=(B-T)+W;
		return;
	}
	if(P.size()==1) {
		ma=max(ma,max(B-P[0].second,P[0].second-T)+W);
		ma=max(ma,max(P[0].first,W-P[0].first)+B-T);
		return;
	}
	
	vector<int> Y;
	FORR(r,P) Y.push_back(r.second);
	sort(ALL(Y));
	int my=Y[Y.size()/2], x;
	vector<pair<int,int>> PT,PB;
	
	
	FORR(r,P) {
		if(r.second<my) PT.push_back(r);
		if(r.second>my) PB.push_back(r);
	}
	dfs(T,my,PT);
	dfs(my,B,PB);
	
	vector<pair<int,pair<int,int>>> LL,RR;
	vector<int> RM;
	int mid = lower_bound(ALL(P),make_pair(W/2,0))-P.begin();
	
	int CT=T,CB=B;
	for(x=mid-1;x>=0 && CT!=CB;x--) {
		while(LL.size() && LL.back().second==make_pair(CT,CB)) LL.pop_back();
		LL.push_back({P[x].first,{CT,CB}});
		if(P[x].second<=my && P[x].second>CT) CT=P[x].second;
		if(P[x].second>=my && P[x].second<CB) CB=P[x].second;
	}
	if(CT!=CB) {
		while(LL.size() && LL.back().second==make_pair(CT,CB)) LL.pop_back();
		LL.push_back({0,{CT,CB}});
	}
	
	CT=T,CB=B;
	for(x=mid;x<P.size() && CT!=CB;x++) {
		while(RR.size() && RR.back().second==make_pair(CT,CB)) RR.pop_back(), RM.pop_back();
		RR.push_back({P[x].first,{CT,CB}});
		RM.push_back(CB-CT+P[x].first);
		
		if(P[x].second<=my && P[x].second>CT) CT=P[x].second;
		if(P[x].second>=my && P[x].second<CB) CB=P[x].second;
	}
	if(CT!=CB) {
		while(RR.size() && RR.back().second==make_pair(CT,CB)) RR.pop_back(), RM.pop_back();
		RR.push_back({W,{CT,CB}});
		RM.push_back(CB-CT+W);
	}
	for(x=RM.size()-2;x>=0;x--) RM[x]=max(RM[x],RM[x+1]);
	
	int TL=0, TR=0;
	FORR(l,LL) {
		while(TL<RR.size()-1 && RR[TL+1].second.first<=l.second.first && RR[TL+1].second.second>=l.second.second) TL++;
		while(TR<RR.size() && (RR[TR].second.first<l.second.first || RR[TR].second.second>l.second.second)) TR++;
		
		for(x=TL;x<=min((int)RR.size()-1,TR);x++) {
			auto r=RR[x];
			int dx=r.first-l.first;
			int dy=min(l.second.second,r.second.second)-max(l.second.first,r.second.first);
			if(dy>0) ma=max(ma,dx+dy);
		}
		if(TR<RR.size()) ma=max(ma,RM[TR]-l.first);
		
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	ma=max(W,H)+1;
	
	FOR(j,2) {
		vector<pair<int,int>> P;
		FOR(i,N) P.push_back({X[i],Y[i]});
		sort(ALL(P));
		
		dfs(0,H,P);
		
		swap(W,H);
		FOR(i,N) swap(X[i],Y[i]);
	}
	
	cout<<ma*2<<endl;

}

まとめ

結構尺取り法のあたり解説をかっ飛ばしてしまっている。
Editorialにはスライド最大値が云々と書かれているが、それがなくても計算量的には間に合ってしまった。
(for(x=TL;x<=min((int)RR.size()-1,TR);x++)の部分)