TopCoder SRM 547 Div1 Medium RectangularSum
問題
幅h, 高さwのグリッドがある。
グリッドには
0 1 2 ... w-1
w w+1 w+2 ... 2w-1
...
のように数字が書かれている。
このグリッドの長方形の部分で、書かれている数字の総和がSであるような部分のうち、
最も面積が小さいものの面積を求めよ。
そのような長方形が存在しない場合-1を返せ。
制約条件
h, w≦10^6
S≦10^12
方針
左上をの数字をxとして、高さa, 幅bの長方形に書かれている数字の和は、
x, a, b(とw, h)の簡単な式で表すことが出来る。
表すと、
2S = a * b * (〜)という形になり、
a, bは2Sの約数に限られることがわかる。
したがって、このようなa, bを、2Sの約数を列挙して探せばよい。
あまり適当に約数を探すとTLEになってしまうが、
2Sを素因数分解してからa, bを組み立てれば、最悪200msくらいで終わる。
ソースコード
int n, h, w; ll S, p[100], e[100], ans; void rec(ll a, ll b, int cur){ if(cur == n){ ll x = 2 * S / a - w * b * (a - 1) - b * (b - 1); if(x < 0 || x % (2 * b)) return; x /= 2 * b; ll r = x / w, c = x % w; if(0 <= r && r + a <= h && 0 <= c && c + b <= w) ans = min(ans, a * b); return; } rep(i, e[cur] + 1){ ll nb = b; rep(j, e[cur] - i + 1){ rec(a, nb, cur + 1); nb *= p[cur]; } a *= p[cur]; } } class RectangularSum { public: long long minimalArea(int height, int width, long long S) { ::S = S; h = height; w = width; n = 0; ll s = 2 * S; for(ll i = 2; i * i <= s; i++) if(s % i == 0){ int c = 0; while(s % i == 0) s /= i, c++; p[n] = i; e[n++] = c; } if(s > 1) p[n] = s, e[n++] = 1; ans = inf; rec(1, 1, 0); return ans == inf ? -1 : ans; } };