kmjp's blog

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

HackerRank HourRank 23 : B. Largest Pyramid

その他コンテスト

見慣れないテクが多くて勉強になりました。
https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid

問題

N*Mのグリッド上の各マス(y,x)に、底面と同じサイズの各面を持つ立方体が積まれており、その高さH(y,x)が与えられる。
このマスに最大K個以下の立方体を積み増しし、どこかに底面(2H-1)*(2H-1)、高さHのピラミッド形状に立方体が積まれた状態を作りたい。
可能な最大の高さを求めよ。

解放

最大値を求める問題だが、二分探索ではうまくいかない。
この問題では、以下の２つをともに満たす高さを求める必要がある。

  • ピラミッド構築に不足する立方体がK個以下である。
  • 元からある立方体によって、目標のピラミッド型をはみ出てはならない。

高さが高いほど不足する立方体が増え、低ければ低いほどはみ出る可能性が高い。
ということで高すぎても低すぎてもダメなため、二分探索は使えない。
ここはピラミッドの中心座標(y,x)および高さhを総当たりし、上記２条件を満たすhの最大値を求めよう。

前者についてはチェックは容易である。
先に前処理として矩形内の立方体の数の総和を求めておけば、ピラミッド構築に必要な立方体数との比較でO(1)で検証できる。
問題は後者である。

高さhのピラミッドを作る場合、(y,x)からa,bだけ離れた位置(y+a,x+b)における高さは、h-max(abs(a),abs(b))以下でなければならない。
逆に言えば、H(y,x)+max(abs(a),abs(b))がh以下ならばよい。
そこで、各座標(p,q)に対し、H(p,q)+p、H(p,q)-p、H(p,q)+q、H(p,q)-qの4値を求め、個別にテーブルを作っておこう。

そうすればp=y+a,q=x+bのときH(y,x)+max(abs(a),abs(b))=max(H(p,q)+p,H(p,q)-p,H(p,q)+q,H(p,q)-q)となる。
あとは２次元のRMQで４つのテーブルの最大値を求めるよう前処理をしておけば、この判定もO(1)で済む。

よって全体では1クエリに対しO(N*M*min(N,M))で解ける。

template<class V,int NV> class RMQ_2D {
private:
	V table[NV][1<<NV][1<<NV];
	int NV2;
public:
	static V const def=-(1<<30);
	V comp(V l,V r){ return max(l,r);};
	RMQ_2D() { init();}
	void init(){ NV2=1<<NV;int i,j,x,y; FOR(i,NV) FOR(x,NV2) FOR(y,NV2) table[i][x][y]=def;}
	void set(int x,int y,V v){ table[0][x][y]=v;}
	void build() {
		int i,j,x,y;
		FOR(i,NV-1) FOR(x,NV2) FOR(y,NV2) {
			int sz=1<<i;
			table[i+1][x][y]=comp(comp(table[i][x][y],table[i][x+sz][y]),
				comp(table[i][x][y+sz],table[i][x+sz][y+sz]));
		}
	}
	V query(int L,int T,int S) { //[L,L+S), [T,T+S)
		int level=0;
		while(1<<(level+1) <= S) level++;
		return comp(comp(table[level][L][T],table[level][L+S-(1<<level)][T]),
			comp(table[level][L][T+S-(1<<level)],table[level][L+S-(1<<level)][T+S-(1<<level)]));
	}
	
};

int Q;
int H,W,K;
int X[400][400];
int S[355][355];

int num[182];
RMQ_2D<int,9> rmq_u,rmq_d,rmq_l,rmq_r;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=180;i++) {
		for(j=1;j<=i;j++) num[i] += (2*j-1)*(2*j-1);
	}
	
	cin>>Q;
	while(Q--) {
		rmq_u.init();
		rmq_d.init();
		rmq_l.init();
		rmq_r.init();
		
		cin>>H>>W>>K;
		FOR(y,H) FOR(x,W) {
			cin>>X[y][x];
			S[y+1][x+1]=X[y][x]+S[y+1][x]+S[y][x+1]-S[y][x];
			rmq_u.set(y,x,X[y][x]+y);
			rmq_d.set(y,x,X[y][x]-y);
			rmq_l.set(y,x,X[y][x]+x);
			rmq_r.set(y,x,X[y][x]-x);
		}
		
		rmq_u.build();
		rmq_d.build();
		rmq_l.build();
		rmq_r.build();
		
		
		int ma=0;
		for(int h=1;h<180;h++) {
			for(y=h-1;y+(h-1)<H;y++) {
				for(x=h-1;x+(h-1)<W;x++) {
					
					int tot=S[y+h][x+h]-S[y-(h-1)][x+h]-S[y+h][x-(h-1)]+S[y-(h-1)][x-(h-1)];
					if(tot+K<num[h]) continue;
					
					int ma_u = rmq_u.query(y-(h-1),x-(h-1),2*h-1)-y;
					int ma_d = rmq_d.query(y-(h-1),x-(h-1),2*h-1)+y;
					int ma_l = rmq_l.query(y-(h-1),x-(h-1),2*h-1)-x;
					int ma_r = rmq_r.query(y-(h-1),x-(h-1),2*h-1)+x;
					
					if(max({ma_u,ma_d,ma_l,ma_r})>h) continue;
					ma=h;
					goto out;
				}
			}
			out:
			;
		}
		cout<<ma<<endl;
	}
}

まとめ

このテクは思い浮かばなかった。
というか2次元RMQが使い慣れない。