HackerRank 101 Hack 51 : D. Small Cubes

今回はこれが一番面白かったかな。
https://www.hackerrank.com/contests/101hack51/challenges/small-cubes

問題

３次元の立方グリッドにおいて、n*m*kの直方体から、一部をくりぬいた形状を考える。
各X座標において、Y,Z座標が(a[X],b[X])-(A[X],B[X])に相当する直方体領域がくりぬかれている。

このくりぬかれた領域を、複数の軸に平行かつ長さが整数の立方体で埋めたい。
埋めた立方体の数をN、最大長をMをしたとき、入力した重みP,Qに応じてP*M+Q*Nのスコアが入る。
得られるスコアの最大値は何か。

解法

スコアの計算方法より、1つだけ大きな立方体を作り、残りを1*1*1の立方体で埋めるのがベストであるのはすぐにわかる。
最大の立方体の辺の長さをL、くりぬかれた全容積をVとすると、P*L+Q*(V+1-L^3)がスコアとなる。
さて、Lの最大値を2分探索で求めよう。そうすればそれ以下の範囲でLを総当たりし、P*L+Q*(V+1-L^3)の最大値を求めればよくなる。

最大の辺の長さLを二分探索するということは、くりぬいた領域中にL*L*Lの立方体が置ければよい。
X座標が[x,x+L-1]の範囲でそのような立方体が置けるかどうかを考える。
これは、i∈[x,x+L-1]の範囲でa[i]の最大値・b[i]の最大値・A[i]の最小値・B[i]の最小値を考えればよい。
(A[i]の最小値-a[i]の最大値+1)および(B[i]の最小値-b[i]の最大値+1)がともにL以上なら、そのような立方体を置ける。

最大値・最小値はRMQで解いてもよいし、スライド最大/最小値でもよい。
後者の方が計算量としては優れるが、以下のコードはSegTreeで解いている。

ll XX,YY,ZZ;
ll P,Q;
ll a[101010],b[101010],A[101010],B[101010];

template<class V,int NV> class SegTree_ma {
public:
	vector<V> val;
	static V const def=-202020;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_ma(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_ma<int,1<<17> L,T,R,D;

int ok(int d) {
	
	for(int i=0;i+d<=XX;i++) {
		int LL=L.getval(i,i+d);
		int RR=-R.getval(i,i+d);
		int TT=T.getval(i,i+d);
		int DD=-D.getval(i,i+d);
		
		if(RR-LL<d) continue;
		if(DD-TT<d) continue;
		return 1;
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>XX>>YY>>ZZ;
	cin>>P>>Q;
	ll V=0;
	FOR(i,XX) {
		cin>>a[i]>>b[i]>>A[i]>>B[i];
		A[i]++,B[i]++;
		V+=(A[i]-a[i])*(B[i]-b[i]);
		
		L.update(i,a[i]);
		R.update(i,-A[i]);
		T.update(i,b[i]);
		D.update(i,-B[i]);
	}
	
	int mav=1;
	for(i=20;i>=0;i--) if(ok(mav+(1<<i))) mav+=1<<i;
	
	ll ret=0;
	for(i=1;i<=mav;i++) ret=max(ret,i*P+(V-(ll)i*i*i+1)*Q);
	cout<<ret<<endl;
	
}

まとめ

1辺Lの立方体の存在判定を思いつけたのでよかった。このテクは今後も使えそう。