HackerRank 101 Hack 55 : C. Tower Construction

Cまですんなり解けたのが良かったかも。
https://www.hackerrank.com/contests/101hack55/challenges/tower-construction

問題

無限に続く２次元グリッドにおいて、いくつかのマスが黒く塗られている。
黒く塗られたマスは隣接マスを辿りすべて連結している。
黒く塗られたマス同士を、黒く塗られた隣接マスだけを辿って移動するとき、常に最短距離で移動できるよう黒マスを追加したい。
追加する黒マス数の最小値を求めよ。

解法

グリッド上において、凸でない黒塗り領域を凸にする問題。
Line Sweepの要領で解ける。
各Y座標において、最も左の黒マスのX座標をL[y]、右の黒マスをR[y]とする。
a＜y＜bとなるa,bにおいて、L[y]≦max(L[a],L[b])、R[y]≧min(R[a],R[b])であれば凸になる。
ここからL[y],R[y]の値を補正すれば、各Y座標において塗るべきマス数が求まる。

int N;
ll X[505050],Y[505050];

map<ll,ll> L,R;
vector<ll> A,B;
ll lef[505050],ri[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	FOR(i,N) cin>>Y[i];
	FOR(i,N) {
		if(L.count(Y[i])) L[Y[i]]=min(L[Y[i]],X[i]);
		else L[Y[i]]=X[i];
		if(R.count(Y[i])) R[Y[i]]=max(R[Y[i]],X[i]);
		else R[Y[i]]=X[i];
	}
	FORR(m,L) A.push_back(m.second);
	FORR(m,R) B.push_back(m.second);
	lef[0]=A[0];
	for(i=1;i<A.size();i++) lef[i]=min(lef[i-1],A[i]);
	ri[A.size()-1]=A[A.size()-1];
	for(i=(int)A.size()-2;i>=0;i--) ri[i]=min(ri[i+1],A[i]);
	FOR(i,A.size()) A[i]=max(lef[i],ri[i]);

	lef[0]=B[0];
	for(i=1;i<B.size();i++) lef[i]=max(lef[i-1],B[i]);
	ri[B.size()-1]=B[B.size()-1];
	for(i=(int)B.size()-2;i>=0;i--) ri[i]=max(ri[i+1],B[i]);
	
	ll ret=-N;
	FOR(i,B.size()) {
		B[i]=min(lef[i],ri[i]);
		ret+=B[i]-A[i]+1;
	}
	cout<<ret<<endl;
	
}

まとめ

このテクは他にも使えそう。