kmjp's blog

競技プログラミング参加記です

TopCoder SRM 687 Div2 Hard Queueing

問題文のひっかけがいやらしい。
https://community.topcoder.com/stat?c=problem_statement&pm=14167

問題

2人のスーパーの従業員が、それぞれ自身のレジに並んだ客を捌いていく。
スキルpの従業員は、1回処理するごとに確率1/pで客を1人捌ける。
すなわちk回の処理で客を捌ける確率は(1/p)**1である。

スキルp1の従業員がlen1人捌くのと、スキルp2の従業員がlen2人捌くので、前者が先に列全員を捌き終える確率を求めよ。

解法

それぞれ何回で全員捌き終わるかを数えたくなるが、処理500000回程度まで計算しても精度不足で正解しない。

問題文を見るとつい回数を数えたくなるが、回数が何回だろうと今目の前の客を捌ける確率は1/pで変わりはない。
そのため回数を比較するのではなく、残り人数に対するDPを行おう。

dp(a,b) := 前者の従業員が残りa人、後者の従業員が残りb人捌く時、前者が先全員捌き終える確率
とする。求めたいのはdp(len1,len2)である。

1回処理を行うと以下の何れかが生じる。

  • 両従業員が客を捌く : 確率(1/p1)*(1/p2)
  • 前者の従業員だけが客を捌く : 確率(1/p1)*(1-(1/p2))
  • 後者の従業員だけが客を捌く : 確率(1-(1/p1))*(1/p2)
  • どちらも客を捌けない : 確率(1-(1/p1))*(1-(1/p2))

最後のケースは状態が変わらないので、残り3通りの重みづけ平均を取ればよい。
すなわち 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];
		
	}
}

まとめ

回数に気をそらさせておいて、解法に回数が登場しないのがいやらしい。

*1:1-1/p)^(k-1

*2:1/p1)*(1/p2)*dp(a-1,b-1) + (1/p1)*(1-(1/p2

広告を非表示にする