kmjp's blog

競技プログラミング参加記です

Google Code Jam 2015 Round 2 : B. Kiddie Pool

本番この方針は思いつかなかったなぁ。
https://code.google.com/codejam/contest/8234486/dashboard#s=p1

問題

N個の蛇口がある。
各蛇口はC[i]度の水を秒間R[i]の容量で出す。
各蛇口から出る水はすべて使っても良いし使わなくても良い。

X度の水をVリットル作るのにかかる最短時間を求めよ。

なお、複数の水をまとめると、その温度は各水を容積で重みづけした値になる。
また水は時間経過で温度が変わることはない。

解法

まず各C[i]からXを引いておく。
こうすると、求めるのは0度の水をVリットル作る問題と言い換えることができる。
考え方として、まず1秒で0度の水をどれだけたくさん作れるか求め、その値でVを割れば解となる。

では0度の水はどれだけたくさん作れるか。
まずもともと0度の水が出る蛇口の水はすべて使えばよい。
後は0度より冷たい水*1と0度より暖かい水を混ぜ、0度の水をできるだけ多く作りたい。

各蛇口の熱容量をR[i]*C[i]とする。
0度未満の蛇口の熱容量の総和(の絶対値)と、0度より暖かい蛇口の熱容量の総和を考えると、それぞれ両者のうち小さい方に合わせた熱容量となるよう水を混ぜればよい。

同じ熱容量の水を沢山作るなら、元の温度が0度に近い方がたくさんの容積の水を使える。
よって、0度未満、および0度超それぞれ、0度に近い順に蛇口を使い、それぞれ熱容量の総和が先に求めた「小さい方に合わせた熱容量」となるように水を用いていく。

「極端に冷たいor熱い水を入れると0度に出来ないから、総和が0度になるよう極端な温度の水を使わないようにする」と考えても良い。

int N;
double V,X;
vector<pair<double,double>> P,P2;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	cin>>N>>V>>X;
	
	P.clear();
	P.resize(N);
	double VV[3]={};
	double VX[3]={};
	
	FOR(i,N) {
		cin>>P[i].second>>P[i].first;
		P[i].first -= X;
		if(P[i].first<0) VX[0]+=abs(P[i].second*P[i].first);
		if(P[i].first>0) VX[1]+=abs(P[i].second*P[i].first);
	}
	sort(P.begin(),P.end());
	
	VX[0]=VX[1]=min(VX[0],VX[1]);
	double vr=0,v;
	FOR(i,N) {
		if(P[i].first==0) vr+=P[i].second;
		if(P[i].first>0) {
			v=min(P[i].second,VX[1]*1.0/P[i].first);
			VX[1] -= v*P[i].first;
			vr += v;
		}
	}
	for(i=N-1;i>=0;i--) if(P[i].first<0) {
		v=min(P[i].second,-VX[0]*1.0/P[i].first);
		VX[0] += v*P[i].first;
		vr += v;
	}
	
	if(vr==0) _P("Case #%d: IMPOSSIBLE\n",_loop);
	else _P("Case #%d: %.12lf\n",_loop,V/vr);
}

まとね

うーん、本番二分探索に頭が捉われてしまった。

*1:この温度はXを引いた値なので、氷ではない