TopCoder SRM 560 Div1 Medium DrawingPointsDivOne

問題

座標平面上の点の集合pに対して、次のようにして点の集合qをつくる。
(x, y), (x+1, y), (x, y+1), (x+1, y+1)に点があるとき、
(x+0.5, y+0.5)をqに加える。
p := qとする。

座標平面上にn個の点(x[i], y[i])がある。
この点の集合は、ある集合に対して上の操作を何度か繰り返して得られたものである。
操作は最大で何回行われたか、求めよ。

最大値がない場合は-1を返せ。

制約条件

座標の絶対値≦70
点の個数≦50

方針

Editorial読んだ。
(x, y)に点があるとき、一つ前の状態では、
(x-0.5, y-0.5), (x-0.5, y+0.5), (x+0.5, y-0.5), (x+0.5, y+0.5)に点があった。

点同士の相対関係のみ考えればよいので、(x, y), (x+1, y), (x, y+1), (x+1, y+1)に点があったとしてよい。
これは300^2回ループのdpで求まる。

直前の状態がわかったら、その状態から本当に最初の状態に戻るかを確かめる。
tステップ前を考えていて、最後に(x, y)に点のある状態に戻るためには、
(x, y)から(x + t, y + t)の間に全て点がなくてはならない。

これは(x, y)を左上とする長方形の最大のサイズを調べるDPをすれば300^2の計算量で求まる。
なので1ステップあたり300^2くらいで、妥当か判定でき、
それが高々300ステップしかないので300^3回のループで答えが計算できる。

ソースコード

vector<pi> p;
bool t[610][610], init[610][610];
int dp[610][610];

bool check(int sz){
	for(int i = 600; i >= 0; i--)
	for(int j = 600; j >= 0; j--)
	t[i][j] |= i && t[i - 1][j] || j && t[i][j - 1] || i && j && t[i - 1][j - 1];
	
	memset(dp, 0, sizeof(dp));
	for(int i = 600; i >= 0; i--) for(int j = 600; j >= 0; j--){
		if(t[i][j]){
			dp[i][j] = min(min(dp[i + 1][j], dp[i][j + 1]), dp[i + 1][j + 1]) + 1;
		}
		if(init[i][j] != (dp[i][j] > sz + 1)) return 0;
	}
	return 1;
}

class DrawingPointsDivOne {
	public:
	int maxSteps(vector <int> x, vector <int> y) {
		memset(t, 0, sizeof(t));
		int n = x.size();
		int mnx = *min_element(all(x)), mny = *min_element(all(y));
		rep(i, n) t[x[i] - mnx][y[i] - mny] = 1;
		
		memcpy(init, t, sizeof(init));
		
		rep(i, 300){
			if(!check(i)) return i;
		}
		return -1;
	}
};