AtCoder ABC #356 : G - Freestyle

方針は正しかったけど、時間内に詰め切れなかった。
https://atcoder.jp/contests/abc356/tasks/abc356_g

問題

プレイヤーはN種類の泳ぎ方ができる。
i番目の泳ぎ方は、1秒当たり体力をA[i]消費してB[i]メートル進む。
泳ぎ方は任意のタイミングで切り替えられ、切り替えにかかる時間は0である。

以下のクエリに答えよ。

• 消費する体力をC以下でDメートル進むことができるか。できるなら最短時間を求めよ。

解法

N種類の泳ぎ方に対し、X座標をB[i]、Y座標をA[i]として2次元座標上にプロットすると、これらの泳ぎ方を混ぜることでできる体力消費と進む距離の組み合わせは、これらの凸包及びY座標が小さい範囲である。
とすると、極力体力消費を抑えて遠くまで進みたいので、最良の進み方は凸包のうち原点との偏角がC/Dとなる点である。

偏角がC/Dとなる点は2つあり得るが、その場合は速度が速い方を選ぶのがよい。
あとは各クエリ、凸包の辺に対し二分探索を行い、偏角がC/Dとなる点を求めよう。

int N,Q;
vector<pair<ll,ll>> Vs;

const ll EPS=0;
template<class C> C veccross(pair<C,C> p1,pair<C,C> p2,pair<C,C> p3) {
	p3.first-=p1.first;p2.first-=p1.first;
	p3.second-=p1.second;p2.second-=p1.second;
	return p3.first*p2.second-p2.first*p3.second;
}

template<class C> vector<int> convex_hull(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	if(vp.size()<=2) {
		if(vp.size()>=1) res.push_back(0);
		if(vp.size()>=2 && vp[0]!=vp[1]) res.push_back(1);
		return res;
	}
	
	FOR(i,vp.size()) sorted.push_back(make_pair(vp[i],i));
	sort(sorted.begin(),sorted.end());
	
	res.resize(vp.size()*2);
	/* bottom */
	FOR(i,vp.size()) {
		while(k>1 && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	/* top */
	for(rb=k, i=vp.size()-2;i>=0;i--) {
		while(k>rb && veccross(vp[res[k-2]],vp[res[k-1]],sorted[i].first)<=-EPS) k--;
		res[k++]=sorted[i].second;
	}
	res.resize(k-1);
	return res;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<ll,ll>> V;
	FOR(i,N) {
		cin>>x>>y;
		V.push_back({x,y});
	}
	auto ind=convex_hull(V);
	FORR(i,ind) {
		Vs.push_back({V[i].second,-V[i].first});
	}
	V.clear();
	sort(ALL(Vs));
	reverse(ALL(Vs));
	FORR2(d,c,Vs) {
		c=-c;
		if(V.size()&&d*V.back().second<=V.back().first*c) continue;
		V.push_back({d,c});
	}
	reverse(ALL(V));
	
	
	cin>>Q;
	while(Q--) {
		ll C,D;
		cin>>C>>D;
		if(D*V[0].second>C*V[0].first) {
			_P("-1\n");
			continue;
		}
		if(C*V.back().first>=D*V.back().second) {
			double tim=1.0*D/V.back().first;
			_P("%.12lf\n",tim);
			continue;
		}
		x=0;
		for(j=20;j>=0;j--) if(x+(1<<j)<V.size()-1) {
			if(C*V[x+(1<<j)].first>=D*V[x+(1<<j)].second) x+=1<<j;
		}
		double LL=0,RR=1;
		FOR(j,100) {
			double MM=(LL+RR)/2;
			double DD=V[x].first*MM+V[x+1].first*(1-MM);
			double CC=V[x].second*MM+V[x+1].second*(1-MM);
			if(C*DD>=D*CC) RR=MM;
			else LL=MM;
		}
		double DD=V[x].first*LL+V[x+1].first*(1-LL);
		double CC=V[x].second*LL+V[x+1].second*(1-LL);
		double tim=1.0*D/DD;
		_P("%.12lf\n",tim);
	}
	
	
}

まとめ

解法は思いつても、その後細かいところを詰めるのに手間取りすぎた。