TopCoder SRM 528 Div2 Hard Mosquitoes

なんとなくCodeforcesに出そうな問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11654

問題

１直線上をN匹の蚊が等速直線運動しており、それぞれの蚊の初期位置P[i]と移動速度V[i]が与えられる。
任意の時間T>=0において、ある座標に爆弾を仕掛けるとそこから±Rの範囲の蚊を退治することができる。
適切に爆弾を配置したとき、退治できる蚊の最大数を求めよ。
なお、爆発する時間は整数でなくても良い。

解法

時間が整数でないのでDPは行えない。
ここでは、各蚊が爆発の左端に来るようなケースを考える。
i番目が左端とすると、他のj番目の蚊がそこから2Rの範囲内に入る時間、すなわちP[i]+t[j]*V[i] <= P[j]+t[j]*V[j] <= P[i]+t[j]*V[i]+2Rとなるt[j]の範囲を求める。
後は出来るだけ多くのt[j]を巻き込める時間Tを求めればよい。

左端候補がN通りあり、各蚊を左端としたときの退治する蚊の列挙がO(N^2)なので全体でO(N^3)で処理可能。

class Mosquitoes {
	public:
	int test(vector<pair<double,double> >& V) {
		int ma=0;
		int i,x,j;
		FOR(i,V.size()) FOR(j,2) {
			double v=(j==0)?V[i].first:V[i].second;
			int r=0;
			FOR(x,V.size()) {
				if(abs(v-V[x].first)<1e-9 || abs(v-V[x].second)<1e-9 || (V[x].first<=v && v<=V[x].second)) r++;
			}
			ma=max(r,ma);
		}
		return ma;
	}
	
	int getMaximum(vector <int> xInit, vector <int> v, int R) {
		int N=v.size();
		int ma=1,t,x,l;
		
		FOR(l,N) {
			int al=0;
			vector<pair<double,double> > V;
			FOR(x,N) {
				if(v[l]==v[x]) {
					if(xInit[l]<=xInit[x] && xInit[x]<=xInit[l]+2*R) al++;
				}
				else {
					double t0 = (xInit[l]-xInit[x])/(double)(v[x]-v[l]);
					double tr = (xInit[l]+2*R-xInit[x])/(double)(v[x]-v[l]);
					if(t0>=0 || tr>=0) {
						t0=max(0.,t0);
						tr=max(0.,tr);
						V.push_back(make_pair(min(t0,tr),max(t0,tr)));
					}
				}
			}
			ma=max(ma,al+test(V));
		}
		
		return ma;
	}
};

まとめ

蚊の退治に爆弾とは物騒だが、ともあれ面白い問題だった。