TopCoder SRM 560 Div1 Medium DrawingPointsDivOne

さてMedium。珍しく割とすんなり回答が思いついて、かつ解けた問題。
Result見たら何気にこのSRM560、自分はDiv1で一番レートが上がってた。
低いレートの割に良い順位を取ったからか…。

http://community.topcoder.com/stat?c=problem_statement&pm=12295

座標上の点集合に対し、点を削減していくオペレーションが定義されている。
ある点集合が与えられたとき、その点集合を再現できる最多オペレーション回数を答える問題。
回答は割とシンプルで、N回オペレーションできるかどうかは、N手戻してまたN手進めたときもとに戻るかを求めるだけ。

最多のNを二分探索で求めてる人もいたけど、1から順に行っても計算量は問題なかった。
ただ、N手進める処理は座標上で(N+1)x(N+1)分正方形上に点が埋まっている領域を求めるので、ここの計算量は工夫した。

MxMのセルからNxNの正方形を素直に求めるとO(M^2xN^2)かかってしまう。
この処理は、まず横方向にN個連続セルが埋まっているかを求め、さらに縦方向にN個分横方向にN個以上連続したセルが埋まっているかどうかを求めればO(M^2)で求まる。

なお、何手でも戻せる場合があるが、今回のデータセットは点間の距離が最大140なので、140を超えてももとに戻せるなら、いくらでも戻せる、と判断した。

Twitterなどでは最後のテストケースが３になる…という声が多かったけど、幸い自分はそのケースにはぶつからなかった。

class DrawingPointsDivOne {
	public:
	int m[300][300];
	int cs[300][300];
	
	int check(int cstep) {
		int num[300][300];
		int num2[300][300];
		int x,y;
		ZERO(num);
		ZERO(num2);
		//yoko
		for(y=299;y>=0;y--) {
			for(x=299;x>=0;x--) {
				if(x==299) num[x][y]=cs[x][y];
				else if(cs[x][y]==0) num[x][y]=0;
				else num[x][y] = num[x+1][y]+1;
			}
		}
		//tate
		for(x=299;x>=0;x--) {
			for(y=299;y>=0;y--) {
				if(y==299) num2[x][y]=(num[x][y]>=cstep)?1:0;
				else if(num[x][y]<cstep) num2[x][y]=0;
				else num2[x][y] = num2[x][y+1]+1;
				int r=(num2[x][y]>=cstep)?1:0;
				if(r!=m[x][y]) return 0;
			}
		}
		return 1;
	}
	
	int test(int cstep) {
		int ns[300][300];
		int x,y;
		
		ZERO(ns);
		FOR(x,299) {
			FOR(y,299) {
				if(cs[x][y]) {
					ns[x][y]=ns[x+1][y+1]=ns[x+1][y]=ns[x][y+1]=1;
				}
			}
		}
		
		memcpy(cs,ns,sizeof(cs));
		return check(cstep+1);
	}
	
	int maxSteps(vector <int> x, vector <int> y) {
		int i;
		ZERO(m);
		ZERO(cs);
		FOR(i,x.size()) m[x[i]+70][y[i]+70]=cs[x[i]+70][y[i]+70]=1;
		
		
		int step=0;
		while(test(step+1)) {
			step++;
			if(step>150) return -1;
		}
		return step;
	}
};

まとめ

気持ち良く終われた回。
「何手進めるか」ではなく「何手戻せるか」なので割と珍しい問題。