Codeforces #425 Div2 C. Strange Radiation

色々グダグダすぎた。
http://codeforces.com/contest/832/problem/C

問題

[0,10^6]の範囲の1次元の座標上でN人の人がいる。
各人初期位置X[i]と走る向きT[i]、速さV[i]が決まっている。

ここで[0,10^6]の範囲の整数座標のいずれかで１か所爆弾を仕掛けるとする。
爆弾が爆発すると同時に、各人が決められた方向・速さで走り出すとする。
同時に爆弾は両方向に速さSの爆風を出す。

走っている人が後ろから追い風になる爆風を受けると、その瞬間その人の速さはS加速する。
爆弾の位置を最適に配置した場合、座標の両端、0および10^6の両方に最低１人ずつは到達する最短時間を求めよ。

解法

２つアプローチがあるようだ。
1つはConvex Hull Trickの要領で爆弾の配置ごとに最速で両端に到達する人を求める方法。
もう一つは時間で二分探索する方法である。

以下は後者について説明する。
まず、爆弾の配置による二分探索はできない。爆弾の配置と両端の到着時刻は単調増加・減少や上に凸・下に凸といった単純な対応にならないためである。
そこで、時間による二分探索を考える。
到達時間を定めたとき、各人がその時間までに左右いずれかの端に到達するためには爆弾がどの範囲になければならないかが求められる。

左方向に行く人における範囲の和集合と、右方向に行く人における範囲の和集合のうち、整数地点で両方に含まれる場所が１個でもあれば、その到達時間を守ることができる。
Editorialでは尺取り法っぽい方法を取っているが、以下のコードではimos法の要領で各点をカバーする人の数を求めた。

int N,S;
double L[1010101],R[1010101];
int X[101010],V[101010],T[101010];

int LL[1010000],RR[1010000];

int ok(double TT) {
	ZERO(LL);
	ZERO(RR);
	
	int i;
	FOR(i,N) {
		if(T[i]==1) {
			if(X[i]*1.0/V[i]-1e-9<=TT) LL[0]++;
			else if(X[i]*1.0/(S+V[i])-1e-9<=TT) {
				LL[X[i]]++;
				double a=TT*(V[i]+S)-X[i];
				double y=a*(S-V[i])/S;
				
				LL[min(1000001LL,X[i]+(ll)floor(y)+1)]--;
			}
		}
		else {
			if((1000000-X[i])*1.0/V[i]-1e-9<=TT) RR[1000000]++;
			else if((1000000-X[i])*1.0/(S+V[i])-1e-9<=TT) {
				RR[X[i]]++;
				double a=TT*(V[i]+S)-(1000000-X[i]);
				double y=a*(S-V[i])/S;
				if(X[i]-floor(y)-1>=0) RR[X[i]-(ll)floor(y)-1]--;
			}
		}
	}
	for(i=1;i<=1000000;i++) LL[i]+=LL[i-1];
	for(i=1000000;i>=0;i--) RR[i]+=RR[i+1];
	FOR(i,1000001) if(LL[i]&&RR[i]) return 1;
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	FOR(i,N) cin>>X[i]>>V[i]>>T[i];
	
	double L=0,R=1e6;
	FOR(i,60) {
		double M=(L+R)/2;
		if(ok(M)) R=M;
		else L=M;
	}
	
	_P("%.12lf\n",L);
	
}

まとめ

まぁDiv2CでCHTはないよなぁ…。