あと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; } }
まとめ
容量マイナスを除けば妙なコーナーケースもないし安心できる問題。