kmjp's blog

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

TopCoder SRM 776 : Div1 Medium Div2 Hard StringRings

SRM

シンプルな式で書ける問題。
https://community.topcoder.com/stat?c=problem_statement&pm=15916&rd=17799

問題

整数A,Bが与えられる。
N=2*A+B本のひもがある。

  • A本は両端とも赤
  • A本は両端とも緑
  • B本は両端が赤・緑１つずつ

であるとする。ひもの端は赤と緑が(A+B)個ずるあることになる。

さて、ここでひもの赤い端と緑の端を連結させることを考える。
この連結のさせ方は、(A+B)!通りある。
そうするといくつかの輪ができることになるが、その本数の期待値を求めよ。

解法

赤だけ・緑だけのひもを含まない輪と、含む輪が考えられる。
まず、前者を考える。
今x本の赤・緑両端のひもがあるとき、これらがなす輪の数の期待値をg(x)とする。
うち１本を取り、その緑側の端がどこにつながるかを考える。
赤いひもがA本でその両端が2A個あり、

  • 自分自身の赤い端とつなぐ。輪が1個増える。
  • 他の赤・緑両端のひもの赤側とつなぐ。実質赤・緑両端のひもが(長さは変わるものの)数としては1個減ったことになる。
  • 両端赤のひものどちらかにつなぐ。両端赤のひもが(長さは変わるものの)数としては変わらず、実質赤・緑両端のひもが1個減ったことになる。

よってそれぞれの確率を考えると \displaystyle g(x) = \frac{1 * (g(x-1)+1) + (x-1) * g(x-1) + 2A * g(x-1)}{2A+x} = \frac{1 + g(x)*(2A+x)}{2A+x}となる。

次に、両端が赤のひもと緑のひもを考える。
前者の過程で緑のひもが長くなるかもしれないが、これは緑のひも数には関係ない。
f(x)を、赤のひもとみどりのひもがx組あるときの輪の期待値とする。
まず赤のひもを1つ選びその端が適当な緑の端と結ばれたとする。この時もう一つの端がどこと結ばれるかを考えると、

  • 片方の端と同じひものもう片方の端につながり、輪を形成する。これは(2x-1)個の選択肢のうちの1つ。
  • 他の緑のひもの端につながる。これは(2x-1)個の選択肢のうちの(2x)通り。この時、最初の緑の余った端点は別の赤いひもとつながる。

よって \displaystyle f(x) = \frac{1*(1+f(x-1))+(2x-2)*f(x-1)}{2x-1} = \frac{1+(2x-1)*f(x-1)}{2x-1}となる。
あとはf(0)=g(0)=1から順にf(x),g(x)を求めてf(A)+g(B)を答えればよい。

double F[1010101];
double G[1010101];

class StringRings {
	public:
	double expectedRings(int A, int B) {
		int i;
		for(i=1;i<=A;i++) F[i]=((F[i-1]+1)+(F[i-1])*2*(i-1))/(2*i-1);
		for(i=1;i<=B;i++) G[i]=((G[i-1]+1)+(G[i-1])*(2*A+i-1))/(2*A+i);
		return F[A]+G[B];
		
	}
}

まとめ

ちょっと手間取ったけど解き切れてよかった。