Codeforces #824 : Div2 F. Pebbles and Beads

あんまり記憶にないな…。
https://codeforces.com/contest/1735/problem/F

問題

この国には小石とビーズの2種類の貨幣があり、初期状態で小石A個、ビーズB個ある。
以後N日の間両者の両替が可能である。

各日の両替レートはP,Qで決まる。
小石X個とビーズY個を交換できる。その際、X*Q=Y*Pでなければならない。また、小石はP個、ビーズはQ個以上交換に出すことはできない。
なお、両貨幣は小数値も取れる。

i日目までの段階で最終的に小石の数を最大化したい場合、それぞれいくつにできるか。

解法

小石・ビーズの組み合わせの可能な範囲を、2次元上の凸多角形で表現する。
初期状態は(0,0)-(a,0)-(a,b)-(0,b)を結ぶ長方形とし、クエリ毎にその多角形をスライドさせていこう。

int T;
int N;
long double X,Y;
int P[303030],Q[303030];

struct cmp {
    bool operator() (pair<long double,long double> a, pair<long double,long double> b) const {
		return a.first*b.second>a.second*b.first;
    }
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y;
		FOR(i,N) cin>>P[i];
		FOR(i,N) cin>>Q[i];
		multiset<pair<long double,long double>,cmp> S;
		S.insert({X,0});
		S.insert({0,Y});
		FOR(i,N) {
			long double deg=atan2(Q[i],P[i]);
			long double len=hypot(P[i],Q[i]);
			S.insert({2*P[i],2*Q[i]});
			long double CY=Y+Q[i];
			long double CX=P[i];
			//FORR2(a,b,S) cout<<a<<":"<<b<<" ";
			//cout<<endl;
			while(CX>1e-9) {
				while(S.empty());
				auto p=*S.begin();
				S.erase(S.begin());
				//cout<<"!"<<CX<<" "<<CY<<" "<<p.first<<" "<<p.second<<endl;
				if(CX>=p.first) {
					CX-=p.first;
					CY-=p.second;
					continue;
				}
				CY-=CX*p.second/p.first;
				p.second-=CX*p.second/p.first;
				p.first-=CX;
				//cout<<"!a"<<CX<<" "<<CY<<" "<<p.first<<" "<<p.second<<endl;
				S.insert(p);
				break;
			}
			Y=CY;
			CX=X+P[i];
			CY=Q[i];
			//FORR2(a,b,S) cout<<a<<":"<<b<<" ";
			//cout<<endl;
			while(CY>1e-9) {
				//cout<<"$$"<<S.size()<<endl;
				
				auto p=*--S.end();
				S.erase(--S.end());
				//cout<<"#"<<CX<<" "<<CY<<" "<<p.first<<" "<<p.second<<endl;
				if(CY>=p.second) {
					CX-=p.first;
					CY-=p.second;
					continue;
				}
				CX-=CY*p.first/p.second;
				p.first-=CY*p.first/p.second;
				p.second-=CY;
				//cout<<"#a"<<CX<<" "<<CY<<" "<<p.first<<" "<<p.second<<endl;
				S.insert(p);
				break;
			}
			X=CX;
			_P("%.12lf\n",(double)X);
			
		}
		
		
	}
}

まとめ

言われてみればそうなんだけど、本番中に細かいところ詰めるのしんどいな。