勉強になりました。
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人選ぶ場合の遷移を考えると
となる。最後が1でなくr/Sとなるのは、ランダムウォークで0ではなくSにたどり着く確率がr/Sとなるためである。
ここで「意見oに統一される確率」の分を考慮したことになる。
式を変形すると
となる。これで3項間漸化式ができるが、今はF(0)とF(S)がわかっているだけでこの式は使いにくい。
そこでF(1)を求めよう。F(1)を変数として、上記式からF(2)、F(3)…と求めていくと
なので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にする手法を始めてみたので勉強になりました。