これは結構あっさり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=12077
問題
H行W列の行列Aがある。0-indexでi行目j列の値は(i*W+j)であり、たとえばH=2,W=3なら
0 1 2 3 4 5
のような行列ができる。
ここで数値Sが与えられる。
行列のうち矩形の範囲を指定し、和がSとなるようにできるか。
できるなら、そのような矩形の最小面積を答えよ。
解法
幅と高さを総当たりしていく。
H,Wの上限は10^6なので、幅と高さを総当たりすると10^12通り考えられるが、Sは高々10^12であり、矩形の幅×高さが10^6を超えると確実に総和は10^12を超えるので、実際は幅×高さが10^6までの範囲を探索すればよい。
幅h、高さwを固定したとき、そのような矩形のうち総和がSになるものが存在しうるか検証する。
まず、矩形の左上を行列の左上に固定すると、その総和s = h*w*W**1/2である。
この矩形を全体的に右に1動かすと、矩形内の数値が1増えるのでsはh*w増加する。
また、全体を下に1動かすと、矩形内の数値がW増えるのでsはW*h*w増加する。
よって、x列右、y列下に動かすしたとき、総和はs+(x+W*y)*h*wとなるので、これがSとなるようなx,yの組があるか計算すればよい。
class RectangularSum { public: ll H,W; int okok(ll h,ll w,ll S) { ll mins = h*w*(w-1)/2 + W*w*h*(h-1)/2; ll st1=h*w; if((S-mins)%st1) return 0; ll momo=(S-mins)/st1; ll right=momo%W; ll down=momo/W; return (right<=W-w && down<=H-h); } long long minimalArea(int height, int width, long long S) { ll mi=1LL<<50; H=height; W=width; ll h,w; for(w=1;w<=W;w++) { for(h=1;h<=H;h++) { if(w*h>mi) break; ll mins = h*w*(w-1)/2 + W*w*h*(h-1)/2; if(mins>S) break; if(okok(h,w,S)) mi=h*w; } } if(mi==1LL<<50) return -1; return mi; } }
まとめ
先にサイズを決めてしまうとだいぶあっさり。
Sが意外と小さいため、検証するh,wの範囲も狭い点に留意。
*1:w-1)+W*(h-1
