TopCoder SRM 642 Div1 Easy WaitingForBus

コーナーケースはともかく、さっくり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=13540

問題

バスターミナルにN台のバスがある。
各バスには、運行時間T[i]と運行確率P[i]が設定されている。
P[i]の総和は100%である。

時刻0にいずれかのバスが確率P[i]で選択され、そのバスが出発する。
するとT[i]後そのバスが戻ってくるので、再びいずれかのバスが確率P[j]で選択され、そのバスが出発する。

上記手順を繰り返す。
同じバスは複数回運行する場合もある。

ここで、時刻Sに乗客がバスターミナルにやってきた。
乗客は時刻S以降で最初に運行するバスに乗る。
乗客がバスに乗るまでの待ち時間の期待値を求めよ。

解法

各時刻tにバスが出発する確率をQ(t)とする。
まず単純なDPでQ(t)を求めることができる。
各バスi及び時刻tについて、t＜Sかつt+T[i]≧Sの場合、時刻tに出発したバスが到着する時刻が乗客の乗るバスの出発時刻となる。
その時、待ち時間はt+T[i]-S、その事象の発生確率はQ(t)*P[i]となるので、左記の値を重みづけ平均すればよい。

double dp[100200];

class WaitingForBus {
	public:
	double whenWillBusArrive(vector <int> time, vector <int> prob, int s) {
		int i,x;
		double ret=0;
		ZERO(dp);
		dp[0]=1;
		if(s==0) return 0;
		FOR(i,s+1) {
			FOR(x,time.size()) {
				if(i+time[x]>=s) ret += (i+time[x]-s)*dp[i]*prob[x]/100;
				else dp[i+time[x]] += dp[i]*prob[x]/100;
			}
		}
		return ret;
		
		
	}
}

まとめ

S==0に見事に引っかかった。