見慣れないテクが多くて勉強になりました。
https://www.hackerrank.com/contests/hourrank-23/challenges/largest-pyramid
問題
N*Mのグリッド上の各マス(y,x)に、底面と同じサイズの各面を持つ立方体が積まれており、その高さH(y,x)が与えられる。
このマスに最大K個以下の立方体を積み増しし、どこかに底面(2H-1)*(2H-1)、高さHのピラミッド形状に立方体が積まれた状態を作りたい。
可能な最大の高さを求めよ。
解放
最大値を求める問題だが、二分探索ではうまくいかない。
この問題では、以下の2つをともに満たす高さを求める必要がある。
- ピラミッド構築に不足する立方体がK個以下である。
- 元からある立方体によって、目標のピラミッド型をはみ出てはならない。
高さが高いほど不足する立方体が増え、低ければ低いほどはみ出る可能性が高い。
ということで高すぎても低すぎてもダメなため、二分探索は使えない。
ここはピラミッドの中心座標(y,x)および高さhを総当たりし、上記2条件を満たす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)となる。
あとは2次元のRMQで4つのテーブルの最大値を求めるよう前処理をしておけば、この判定も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が使い慣れない。