SRM 547 div1 med: RectangularSum
問題
TopCoder Statistics - Problem Statement
H*W の長方形に, 以下のように数字が書いてある。
(1 行目): 0, 1, ..., W-1
(2 行目): W, W+1, ..., 2*W-1
...
(H-1 行目): (h-2)*W, (h-2)*W+1, ..., (h-1)*W-1
ここからうまいこと長方形の区間を取って, その中に書いてある数字の和を S にしたい。そのようなことが可能なら, それを満たす長方形の最小の面積を求めよ。
解法
よくわからないので, 区間 [(h1, w1), (h2, w2)] における数字の和を求めてみましょう。すると,
(w2-w1+1) * (h2-h1+1) * {(w1+w2) + W * (h1+h2)} / 2 であることがわかります(これは計算して)。
中かっこの前の掛け算はまさに長方形の面積ですね。これを w*h (i.e. w = w2-w1+1, h = h2-h1+1)と考えることにすると, 中かっこの中身は,
w+W*h + 2*(w1+W*h1)
となります。w, h はわかっているとすると, h1, w1 は W で割った商, あまりで計算できるので, すべて復元できることになります。
ということで, S = w*h*hoge という形になる w, h, hoge を列挙すれば良いです。計算量がよくわかりませんが間に合いました。
class RectangularSum { public: long long minimalArea(int H, int W, long long S) { ll area = (ll)H*W; S *= 2; vector<ll> cand; for (ll i = 1; i * i <= S; i++) { if (S%i == 0) { cand.push_back(i); if (i*i != S) cand.push_back(S/i); } } ll ans = 1ll<<60; for (ll hw : cand) { if (hw > area) continue; vector<ll> hs; for (ll h = 1; h*h <= hw; h++) { if (hw%h == 0) { hs.push_back(h); if (h*h < hw) hs.push_back(hw/h); } } for (ll h : hs) { ll w = hw/h; if (h > H || w > W) continue; ll q = S/hw - (w-1) - W*(h-1); if (q < 0 || q%2 == 1) continue; q /= 2; ll h1 = q/W, w1 = q%W; ll h2 = h+h1-1, w2 = w+w1-1; if (h2 < h1 || h2 >= H || w2 < w1 || w2 >= W) continue; ans = min(ans, hw); } } if (ans == 1ll<<60) ans = -1; return ans; } };