TopCoder SRM 687 (Div. 2) Hard. Queueing
2つほど解法を思いついたので両方書きます。
問題概要
2 つのレジがあり、レジ i には len[i] 人並んでいる。レジ i が一人を処理するのに掛かる時間は確率的に変化し、k 秒で処理する確率は (1/p)*(1-1/p)k-1 である。
レジ 1 の方が真に早くすべての人を処理する確率を求めよ。
解法 1(強引)
len[i] と書くのは面倒なので n[i] と書き、1/p を p, 1-(1/p) を q とする。
レジ i が n[i] 人を k 秒で処理する確率を Fi(k) としたとき、
$$ \sum_{i=1}^{\infty} \left( F_1(i) \sum_{j=i+1}^{\infty} F_2(j) \right) $$
が答えになる。
レジ i が k 秒で処理するパターンは、
- PqqqqPqqqPq
- PqqPqqPqqqq
- PPqPqqqqqqq
などがあり、先頭の P 以外は自由に並び替えることができるので Fi(k) は次の式で表せる。
$$ F(k)=p \binom{k - 1}{n - 1} p^{n - 1} q^{n - k} $$
よく考えると k=2*106 以降はほぼ 0 なので無視しても問題ない。それさえ分かれば、効率的に式を計算して終わりである。
正確な評価をしなくても、掛かる時間の平均が n/p≦106 であることと二項分布の形から問題ないことは分かるだろう。
TopCoder SRM 687 (Div. 2) Queueing
解法 2(動的計画法)
以下のような DP テーブルを考える。
- dp[ レジ 1 が i 人処理した ][ レジ 2 が j 人処理した ] := この状態に至る確率
遷移パターンは、
- レジ 1 の方が先に一人処理する
- レジ 2 の方が先に一人処理する
- 同時に一人処理する。
の 3 通りある。最終的な答えは dp[n1][0]+...+dp[n1][n2-1] になる。
先ほどの強引解法で確率を求めるときに P と q を並べていたが、ここでもその考え方を使う。
レジ 1 の方が先に一人処理するというのは、
- (P,q)
- (qP,qq)
- (qqP,qqq)
- (qqqP,qqqq)
- (qqq...P,qqq...q)
というパターンである。
$$ 1+p+p^2+\cdots = \frac{1}{1-p} $$
という無限等比級数の公式を使えば遷移確率は p1*q2/(1-q1*q2) だと分かる。他の 2 パターンも同様に考えればいい。
TopCoder SRM 687 (Div. 2) Queueing DP