問題文のひっかけがいやらしい。
https://community.topcoder.com/stat?c=problem_statement&pm=14167
問題
２人のスーパーの従業員が、それぞれ自身のレジに並んだ客を捌いていく。
スキルpの従業員は、１回処理するごとに確率1/pで客を1人捌ける。
すなわちk回の処理で客を捌ける確率は(1/p)**1である。
スキルp1の従業員がlen1人捌くのと、スキルp2の従業員がlen2人捌くので、前者が先に列全員を捌き終える確率を求めよ。
解法
それぞれ何回で全員捌き終わるかを数えたくなるが、処理500000回程度まで計算しても精度不足で正解しない。
問題文を見るとつい回数を数えたくなるが、回数が何回だろうと今目の前の客を捌ける確率は1/pで変わりはない。
そのため回数を比較するのではなく、残り人数に対するDPを行おう。
dp(a,b) := 前者の従業員が残りa人、後者の従業員が残りb人捌く時、前者が先全員捌き終える確率
とする。求めたいのはdp(len1,len2)である。
１回処理を行うと以下の何れかが生じる。
- 両従業員が客を捌く : 確率(1/p1)*(1/p2)
- 前者の従業員だけが客を捌く : 確率(1/p1)*(1-(1/p2))
- 後者の従業員だけが客を捌く : 確率(1-(1/p1))*(1/p2)
- どちらも客を捌けない : 確率(1-(1/p1))*(1-(1/p2))
最後のケースは状態が変わらないので、残り３通りの重みづけ平均を取ればよい。
すなわち dp(a,b) = *2*dp(a-1,b) + (1/p1)*(1-(1/p2))*dp(a,b-1)) / (1-(1-(1/p1))*(1-(1/p2)))
でDPをすればよい。
double win[1010][1010]; class Queueing { public: double probFirst(int len1, int len2, int p1, int p2) { int i,j,x,y; double P[2]={1.0/p1,1.0/p2}; double Q[2]={1-P[0],1-P[1]}; ZERO(win); FOR(i,1000) win[0][i+1]=1; for(x=1;x<=1000;x++) for(y=1;y<=1000;y++) { win[x][y] = P[0]*Q[1]*win[x-1][y]; // get only first win[x][y] += P[1]*Q[0]*win[x][y-1]; // get only second win[x][y] += P[0]*P[1]*win[x-1][y-1]; // get both win[x][y] /= (1-Q[0]*Q[1]); // forget else; } return win[len1][len2]; } }
まとめ
回数に気をそらさせておいて、解法に回数が登場しないのがいやらしい。
