TopCoder SRM 678 Div1 Medium TheEmpireStrikesBack

久々に書くけど、Codeforcesっぽい。
https://community.topcoder.com/stat?c=problem_statement&pm=13373

問題

乱数で生成されるx,y座標が非負の頂点N個が与えられる。
パラメータTを持つ砲台を用いてある点(x,y)に対し砲撃を行うと、(0,0)-(x+T,y+T)の矩形に囲まれた領域の点を破壊できる。
M発の攻撃で全頂点を破壊するのに必要なパラメータTの最小値を求めよ。

解法

２分探索を用いる。

x≦x'かつy≦y'であるような2点(x,y),(x',y')があるとき、後者を破壊すればその際同時に前者も破壊するので、以後前者の存在を意識することはない。
よってそのような(x,y)を取り除こう。
これは頂点をx座標順でソートして行うことができる。

すると、残された頂点群Pはx座標昇順、y座標降順になる。
これらをパラメータTの攻撃M発で破壊できるか考えよう。

尺取法の要領で処理していく。
既にP[1]～P[L-1]までは破壊したとする。
次の砲撃でP[L..R]を破壊するとき、できるだけ大きなRまで巻き込みたい。

まず尺取法の要領で、P[i].y+T≦P[L].yとなる最大のiを求める。
そうするとそのi番目の点が砲撃対象となるので、P[i].x+T≦P[R].xとなるような[L,R]の範囲を破壊できる。
あとはこれがM発で破壊しきれるかチェックするだけ。

vector<pair<ll,ll> > V;
pair<ll,ll> P[101010];
ll mo=1000000007;

class TheEmpireStrikesBack {
	public:
	int ok(int T,int M) {
		int x,y;
		x=0;
		for(y=1;y<V.size();y++) if(V[y].second+T<V[x].second) {
			int tar=V[y-1].first+T;
			while(y<V.size() && V[y].first<=tar) y++;
			if(y==V.size()) return 1;
			if(--M<=0) return 0;
			x=y--;
		}
		return 1;
	}
	
	int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M) {
		int i;
		P[0].first=AX;
		P[0].second=AY;
		for(i=1;i<N;i++) P[i].first=(P[i-1].first*BX+CX)%mo, P[i].second=(P[i-1].second*BY+CY)%mo;
		sort(P,P+N);
		
		V.clear();
		FOR(i,N) {
			while(V.size() && V.back().first<=P[i].first && V.back().second<=P[i].second) V.pop_back();
			V.push_back(P[i]);
		}
		int v=(1<<30)-1;
		for(i=29;i>=0;i--) if(ok(v-(1<<i),M)) v-=1<<i;
		return v;
	}
}

まとめ

これ450ptでもいいような…。CFなら1250pt位な気がする。