mayoko’s diary

プロコンとかいろいろ。

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;
    }
};