kmjp's blog

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

TopCoder SRM 676 Div1 Easy WaterTank

あと1分で本番1000ptHard解けたのに…。でもそれが無くてもなかなか好調でHighestをだいぶ更新できました。
https://community.topcoder.com/stat?c=problem_statement&pm=14019

問題

容積Cの水槽がある。初期状態では中身は空である。
ここにN個の連続した区間の間水を灌いていく。
i番目の区間では、時間T[i]の間時間当たりX[i]の水を灌ぐ。

この際、水槽から水があふれないよう水槽に排水管を取り付けた。
この排水管は時間当たりRの水を排水です。

水槽から水があふれないために必要な最小のRを求めよ。

解法

Rを二分探索し、途中で水があふれないかチェックする。
区間内では時間当たりの水槽の水の容量の変化は線形なので、区間の境目の時の容量だけチェックすればよい。
途中、水が空になった場合マイナスとカウントしないよう注意すること。

class WaterTank {
	public:
	
	double minOutputRate(vector <int> t, vector <int> x, int c) {
		int N=t.size();
		int lp,i;
		double L=0,R=1e10;
		
		FOR(lp,200) {
			double M=(L+R)/2;
			double cur=0;
			FOR(i,N) {
				cur += (x[i]-M)*t[i];
				if(cur<0) cur=0;
				if(cur>c) break;
			}
			if(i==N) R=M;
			else L=M;
		}
		return (L+R)/2;
		
	}
}

まとめ

容量マイナスを除けば妙なコーナーケースもないし安心できる問題。