NJPC 2017 : F - ダブルス

本番時間切れで部分点止まりだったけど、これもうちょい時間掛ければ自力で解けたな。
http://njpc2017.contest.atcoder.jp/tasks/njpc2017_f

問題

テニスのダブルスで、2人で迫りくる球を返していく。
2人は1次元の数直線上を動く。初期位置は原点で、以後最大速度Vで2人それぞれ個別に動くことができる。

打球はN回飛んでくる。
それぞれ時刻T[i]に位置X[i]に飛んでくるので、2人のうち1人はその位置にいなければならない。
すべての打球を打ち返す最小のVを求めよ。

解法

Vを二分探索する。

i番の打球を返した瞬間、1名は位置X[i]にいなければならない。
もう一人がいられる範囲[L,R]の集合を管理していこう。
(i+1)番の打球について、i番の打球を返した人が続けて返球場合と、もう一人が返球する場合それぞれ(i+1)番の打球を返球しなかった方がいられる範囲を求めていけばよい。

これだけだと[L,R]の集合の要素数が増えるので、以下の要領で減らす。

• X[i]の範囲は-10^8～10^8なので、[L,R]は[-10^8,10^8]の中のみ考える。
• 他の要素に含まれるものはそれ以上考えても無駄なので省略する。これは[L,R]の集合をLの昇順にソートして処理していけば、Rの最大値を更新するかどうかで容易に求められる。

int N;
int T[101010];
int X[101010];


double ok(double V) {
	int i,j;
	if(T[0]*V < abs(X[0])) return 0;
	
	set<pair<double,double>> S;
	S.insert({max(-1e8,-T[0]*V),min(1e8,T[0]*V)});
	
	for(i=1;i<N;i++) {
		double ma=-1e11;
		set<pair<double,double>> S2;
		FORR(r,S) {
			if(r.second<=ma) continue;
			
			double lp = r.first - (T[i]-T[i-1])*V;
			double rp = r.second + (T[i]-T[i-1])*V;
			if(lp<=X[i] && X[i]<=rp) {
				double lq = X[i-1] - (T[i]-T[i-1])*V;
				double rq = X[i-1] + (T[i]-T[i-1])*V;
				
				S2.insert({max(-1e8,lq),min(1e8,rq)});
			}
			if(abs(X[i]-X[i-1])<=(T[i]-T[i-1])*V) {
				S2.insert({max(-1e8,lp),min(1e8,rp)});
			}
			ma=max(ma,r.second);
		}
		swap(S,S2);
		if(S.empty()) return 0;
	}
	
	return 1;

}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>T[i]>>X[i];
	double L=1e-10,R=1e10;
	FOR(i,70) {
		double M=(L+R)/2;
		if(ok(M)) R=M;
		else L=M;
	}
	_P("%.9lf\n",L);
}

まとめ

卓球だったら交互に打たなきゃいけないからもっと簡単な問題になるのにね。