SRM 547 500pt : RectangularSum

TopCoder

問題概要

H*W(H,W<10^6)で、X[i,j] = i*W+jであるような行列がある。部分行列で和がちょうどS(<10^12)になるようなもののうち、面積最小のものを求める問題。

考えたこと

  • これもオーバーフローに注意しないと…。
  • 何はともあれ区間決めたときの和を計算しよう。左上のマスをX[h,w]、高さA、幅Bとすると、A*B*( (2*h+A-1)*W+(2*w+B-1)) = 2*Sとなる。
  • これでAやBが2*Sの約数となることが分かるけど、これじゃあまだ探索空間が広すぎる。
  • とはいえ、(2*h+A-1)*W+(2*w+B-1)というのはよい形だ。このままだとアレだけど、(2*w+B-1)の部分が必ずW未満になるようにすれば一意復号できる。
  • 後はいろいろ調べて0<=h && h+A<=H && 0<=w && w+B<=Wとなるかどうかで判定すれば何とか行けそう…。
  • このままだと一意に復号できないのでh*W+w + (h+A-1)*W + (w+B-1) = 2*S/(A*B)とかで変形するのか？うーん端っこが邪魔過ぎる。
  • AとBを全探索できないからA*Bを全探索するのか？
  • ダメだこれだと変数の数が全然減らせない。
  • hとwを全探索…も全探索できない。
  • 結局このまま終了した。
  • 後で他の人の解答見たら、AとBについて枝刈り全探索していた。
  • あっ、そうか。AとBを適当に決めたらA*B*( (A-1)*W+B))は3乗とか4乗で増えるからすぐにSを越えて枝刈りが効く。なるほど賢い。
  • で、これを本番中に思いつくにはどうすればいいんだろう。

acceptされたコード

#include <algorithm>
using namespace std;

typedef long long int64;
const int64 INF = 1LL<<62;

struct RectangularSum {

	int64 minimalArea(int H_, int W_, int64 S) {
		int64 H = H_, W = W_;
		S *= 2;
		int64 ans = INF;
		for (int64 A = 1; A <= H; ++A ) if( S % A == 0 ) {
			for (int64 B = 1; B <= W; ++B ) {
				if( A * B * ((A - 1) * W + (B - 1)) > S ) {
					break;
				}

				if (S % (A * B) != 0) {
					continue;
				}

				int64 T = S / (A * B) - ((A - 1) * W + (B - 1));
				if (T & 1) {
					continue;
				}
				T /= 2;
				int64 h = T / W, w = T % W;
				if (0 <= h && h + A <= H && 0 <= w && w + B <= W ) {
					ans = min( ans, A * B );
				}
			}
		}
		return ans == INF ? -1 : ans;
	}

};