TopCoder SRM 642 Div1 Easy: WaitingForBus (DP・期待値)

解法

動的計画法（渡すDP）。dp[t]:= 時刻tに出発できる確率を計算しておく。

コード

public class WaitingForBus {

	private final int MAX_TIME = 200001;

	public double whenWillBusArrive(int[] time, int[] prob, int s) {
		int N = time.length;

		double[] dp = new double[MAX_TIME];
		dp[0] = 1.0;
		for (int t = 0; t < s; t++) {
			for (int bus = 0; bus < N; bus++) {
				if (t + time[bus] < MAX_TIME) {
					dp[t + time[bus]] += (double) dp[t] * prob[bus] / 100;
				}
			}
		}
		double ans = 0;
		for (int t = s; t < MAX_TIME; t++) {
			ans += dp[t] * (t - s);
		}
		return ans;
	}

}