AtCoder ARC #072 : F - Dam

本番近いところまで行けたかと思ったけど、ちょっと違ってた。
http://arc072.contest.atcoder.jp/tasks/arc072_d

問題

Lリットル貯水できるダムがある。初期状態で貯水量は0である。
i日目の朝は、T[i]度の水がV[i]リットルダムに入る。
その際にダムがあふれないよう、前日夜にダムの水を任意の量排水できる。

各x日目の昼について、それぞれ水温を最大化するように排水したときの最高温度を答えよ。
なお、x日目の昼にはLリットル貯水できてなければいけないが、それ以外の日はLリットルに満たなくてもよい。

解法

ダムの貯水量および(貯水量×水温)を計算し、それを更新していけば、後者を前者で割れば水温が求められる。
あとは、Lリットルを溢れない範囲で、(貯水量×水温)を最大にするよう排水することである。

x日目の昼の水温について答える際、x日以前の日はLリットルに満たなくてもよい。
よって、新しい水が来たらすぐに混ぜて水温を均一化するのではなく、異なる水温のいくつかの水が計Lリットルあるとして考える。
途中あふれそうなら、冷たい水から順に排水すればよい。これはもともとなかったものとして扱うこととする(「x日以前の日はLリットルに満たなくてもよい。」から、この処理が可能)

元からある水に対して、より暖かい水が追加された場合、それらは混ぜなくてもよい(古いものをあとでなかったことにできる)。
しかし元からある水に対して、より冷たい水が追加された場合、それらは混ぜなければならない。
これは、排水はその日の夜であり、一時的にLリットルに収まるよう冷たい水も引き受けなければいけないためである。

上記処理を行うために、(水温,貯水量)の対を水温順にソートしたdequeを用いる。
今i日目の水V[i]を追加することを考える。

• 初日以外はすでにダムが満水のため、朝にV[i]の水を引き受けるためその前日にV[i]排水しておく。
  • これは、dequeの先頭から冷たい順にV[i]だけ排水すればよい。
• 次に、T[i]の水をV[i]追加する。
  • dequeの末尾を見て、T[i]以上の水温の水があったら、即座にこれから加える水と混ぜる。

上記のとおりdequeの前と後ろを操作しつつ、貯水量および(貯水量×水温)を計算する。

int N,L;
double T,V;
double TV,TT;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	
	deque<pair<double,double>> D;
	
	FOR(i,N) {
		cin>>T>>V;
		
		if(i) {
			double del=V;
			
			while(del>0) {
				if(D.front().second<=del) {
					del -= D.front().second;
					TV -= D.front().second;
					TT -= D.front().first*D.front().second;
					D.pop_front();
				}
				else {
					D.front().second -= del;
					TV -= del;
					TT -= D.front().first*del;
					del = 0;
				}
			}
		}
		
		TV += V;
		TT += T*V;
		_P("%.12lf\n",1.0*TT/TV);
		
		while(D.size() && D.back().first>T) {
			double TTT = T*V + D.back().first*D.back().second;
			V = V + D.back().second;
			T = TTT/V;
			D.pop_back();
		}
		D.push_back({T,V});
		
		
	}
	
}

まとめ

こういう問題設定は割と好き。