TopCoder SRM 847 : Div1 Easy Div2 Hard Lasso

不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=18056

問題

グリッド上いくつかのマスにチェスのナイトの駒が置いてある。
1秒毎に、駒はナイトの動きをし、盤面外に出ようとする。(その際、複数駒が一時的に同じマスにいてもよい)

L秒毎に(Lは小数も可)、1つ盤面内の駒を選び取り除くとする。
全駒を、盤面外に出る前に取り除ける最大のLを求めよ。

解法

各駒、上下左右に毎秒2マス動けると考えても、盤面外に出る最短時間は変わらない。
そこで各駒盤面外に出る時間の短い順にソートし、その順で取り除くことを考えよう。
あとはLを二分探索すればよい。

class Lasso {
	public:
	double lasso(int R, int C, int R1, int C1, int R2, int C2) {
		vector<int> S;
		int i,x,y;
		for(int y=R1;y<=R2;y++) {
			for(int x=C1;x<=C2;x++) {
				S.push_back(min({x/2+1,(C-x)/2+1,y/2+1,(R-y)/2+1}));
			}
		}
		sort(ALL(S));
		double X=0,Y=1000;
		FOR(i,100) {
			double M=(X+Y)/2;
			FOR(x,S.size()) if(M*(1+x)>S[x]) break;
			if(x==S.size()) X=M;
			else Y=M;
		}
		return X;
	}
}

まとめ

これDiv2側で1000ptついてたの意外。