kmjp's blog

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

TopCoder SRM 757 Div1 Hard Consensus

勉強になりました。
https://community.topcoder.com/stat?c=problem_statement&pm=15444

問題

計S人の人がおり、それぞれD種類のいずれかの意見を持つ。
ここで以下の手順を繰り返す。

  • S人から順に2名の人を等確率で選ぶ。
  • 後者の人の意見を、前者の人の意見に変える。

この手順を繰り返すと、いずれ全員の意見が一致する。
初期状態として、意見iを持つ人の人数P[i]が与えられるとき、意見が一致するまでの手順の実施回数の期待値を求めよ。

解法

実はこの問題既出だったらしい。Editorialは省略された部分があり、かつ誤りもあるのでもう少し丁寧に各。
Problem - F - Codeforces


全部の意見の状態を考えると面倒なので、最終的に意見oに集約する場合を考えると、意見oかそうでないかの2つの状態だけ持てばよい。
F(r) := 初期状態で意見oを持つ人がr人いる場合、最終的にS人全員が意見oに統一される確率とそれまでの回数の期待値の積
とする。F(r)が求まれば、解はsum(F(P[i]))となる。

F(0)=F(S)=0は明らかである。前者はS人揃うことはないし、後者はすでにS人揃っているためである。
それ以外の場合、S人から2人選ぶ場合の遷移を考えると
 \displaystyle F(r) = \frac{r(S-r)}{S(S-1)} F(r+1) + \frac{r(S-r)}{S(S-1)} F(r-1) + (1-\frac{2S(S-1)r(S-r)}{S(S-1)}) F(r) + \frac{r}{S}
となる。最後が1でなくr/Sとなるのは、ランダムウォークで0ではなくSにたどり着く確率がr/Sとなるためである。
ここで「意見oに統一される確率」の分を考慮したことになる。
式を変形すると
 \displaystyle F(r+1)-F(r) = F(r)-F(r-1) - \frac{S-1}{S-r}
となる。これで3項間漸化式ができるが、今はF(0)とF(S)がわかっているだけでこの式は使いにくい。
そこでF(1)を求めよう。F(1)を変数として、上記式からF(2)、F(3)…と求めていくと
 \displaystyle F(S) = S*F(1) - (S-1)\left(\frac{1}{S-1}+\frac{1}{S-2}+...+\frac{1}{S-(S-1)} \right) = 0
なのでF(1)が求まる。あとは順次F(r)を計算できる。

double dp[2525];

class Consensus {
	public:
	double expectedTime(vector <int> O) {
		ZERO(dp);
		int S=0;
		FORR(v,O) S+=v;
		int i;
		double diff=0;
		for(i=2;i<=S;i++) {
			diff+=(S-1.0)/(S-(i-1));
			dp[i]=dp[i-1]-diff;
		}
		double del=dp[S]/S;
		
		for(i=1;i<=S;i++) dp[i]-=del*i;
		
		double ret=0;
		FORR(v,O) ret+=dp[v];
		
		return ret;
	}
}

まとめ

1じゃなくr/Sにする手法を始めてみたので勉強になりました。