TopCoderOpen 2019 Round3A : Medium WaitingForBusAgain

これは思いつかなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15282&rd=17611

問題

駅にN個のバスが定期的にやってくる。
i番のバスの周期はF[i]であり、そのオフセットは[0～F[i])のうち等確率でいずれかの値(小数含む)を取る。

適当に駅にやってきたとき、最初に来るバスのIDの期待値を求めよ。

解法

最初に誤解法から。
時刻tにi番のバスが来てそれ以外のバスがまだ来てない確率P(i,t)を考え、tで積分する。
これは式としては正しいと思われるが、P(i,t)をtの多項式で求めていく過程で大きな係数が出たり小さすぎる係数がでて、大きな入力に対して破たんする。

以下Writer解説。
Fの最小値をF[m]=Mとする。
各バスは、M未満の時刻で来ないと最初にはなりえない。
一方もしM未満の時刻に来る場合、同じくM未満の時刻に来たバスの中では等確率で先頭になりうる、というのがポイント。
それはM未満で来るバスに関しては、次の到着時刻は[0,M)の中で皆一様なためである。

よって、M未満に到着するバスの数をパラメータとし、その状態になる確率とバス番号の重み付平均を数え上げていこう。

double prob[1020][1020];
double val[1020][1020];

class WaitingForBusAgain {
	public:
	double expectedBus(vector <int> f) {
		int N=f.size();
		int mi=*min_element(ALL(f));
		
		int i,j;
		ZERO(prob);
		ZERO(val);
		prob[0][0]=1;
		FOR(i,N) {
			double p=mi*1.0/f[i];
			FOR(j,N) {
				// take
				prob[i+1][j+1]+=p*prob[i][j];
				val[i+1][j+1]+=p*(val[i][j]*j+prob[i][j]*i)/(j+1);
				// not
				prob[i+1][j]+=(1-p)*prob[i][j];
				val[i+1][j]+=(1-p)*(val[i][j]);
			}
		}
		
		double ret=0;
		for(i=1;i<=N;i++) ret+=val[N][i];
		return ret;
	}
}

まとめ

「M未満の時刻に来たバスの中では等確率で先頭になりうる」っていう考え方がとっさにできる気しないなぁ…。