TopCoder SRM 810 : Div1 Easy Div2 Hard WatchedSnail

Easy落としたけど2Chalのお陰で軽症で済んだ。
https://community.topcoder.com/stat?c=problem_statement&pm=16643&rd=18756

問題

R時間行われるカタツムリのレースがある。
ここでレースの状況を監視している人がC人おり、各自T時間だけレースを監視している。
C*T≧Rであり、レース中常に最低1人はレースを監視している状況にある。

各人が監視中、カタツムリは距離Dだけ前進していた。
カタツムリの移動ペースが任意に可変とするとき、カタツムリは最大どれだけ移動するか。

解法

R=Tの時、解はD。
R＞Tの時、2人の監視員がeps時間だけずらしてカタツムリを監視した場合、そのずれて片方しか見ていない間にD進むことで、(T+eps)時間に2D進むことができる。
そこで、解はmin(C,2*floor*1*Dとなる。

class WatchedSnail {
	public:
	double maxDistance(int raceTime, int observerCount, int observationTime, int observationDistance) {
		if(raceTime==observationTime) {
			return observationDistance;
		}
		
		int ma=min(observerCount, 2*((raceTime-1)/observationTime));
		
		return ma*observationDistance;
	}
}

まとめ

Resubmitまでしたのに結局落としたのもったいないな。

*1:R-eps)/T