AtCoder ABC #275 : G - Infinite Knapsack

方向性はあってたけど間に合わず。
https://atcoder.jp/contests/abc275/tasks/abc275_g

問題

N種類の品物が、それぞれ無限個ある。i種類目の重さはA[i]、体積はB[i]、価値C[i]である。

レベルXの人は、重さの合計と体積の合計のそれぞれがXを超えない範囲で、上記品物を任意の非負整数個分持つことができる。
レベルXの人が持てる品物の価値の総和の最大値をf(X)とするとき、f(X)/Xの極限を求めよ。

解法

小数個の品物の持ち方も可能であると考え、価値1を達成するのに必要なmax(重さの総和,体積の総和)を最小化することを考える。

2次元座標上で各品物に対し、(A[i]/C[i],B[i]/C[i])をプロットしよう。
価値1を達成するのに取れる(重さの総和,体積の総和)は、これらの点が成す凸包の内部となる。

そこで、凸包を成す各点に対応する1種類の品物だけを使う場合と、下側の凸包が直線y=xと交差する点だけ総当たりすればよい。

int N;
double A[202020],B[202020],C[202020];

const double EPS=1e-20;
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_bottom(vector< pair<C, C> >& vp) {
	vector<pair<pair<C, C>, int> > sorted;
	vector<int> res;
	int i,k=0,rb;
	
	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;
	}
	res.resize(k);
	return res;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<double,double>> V,W;
	double ret=1e20;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		ret=min(ret,max(A[i],B[i])/C[i]);
		V.push_back({A[i]/C[i],B[i]/C[i]});
	}
	
	auto A=convex_hull_bottom(V);
	N=A.size();
	FOR(i,N) W.push_back(V[A[i]]);
	V=W;
	FOR(i,N-1) {
		if(V[i].second>V[i].first&&V[i+1].first>V[i+1].second) {
			double dx=V[i+1].first-V[i].first;
			double dy=V[i+1].second-V[i].second;
			double a=0,b=1;
			FOR(j,100) {
				double m=(a+b)/2;
				double nx=V[i].first+dx*m;
				double ny=V[i].second+dy*m;
				if(ny>nx) a=m;
				else b=m;
			}
			ret=min(ret,V[i].first+dx*a);
		}
	}
	
	
	_P("%.12lf\n",1/ret);
	
}

まとめ

最初(A[i]/B[i],C[i]/B[i])でプロットしようとしちゃったけど、確かに(A[i]/C[i],B[i]/C[i])の方が楽だな。