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

苦戦。DP 解は他の人のコードを見て気がついた。