yukicoder : No.352 カード並べ

2回連続遅刻。
そこそこの速度でノーミス全完できたので、普通に参加しておきたかった。
http://yukicoder.me/problems/750

問題

正整数の番号が書かれたカードを以下のように1列に並べる。

• まず1のカードを置く。
• 次に2,3,4...と小さい順にカードを置く。その際、既存のカードの間に置くか、両端に並べる。
  • k番のカードを並べるとき、置ける候補はk個あるが、置く場所はいずれも1/kの確率で選択する。

なお、カードを置く際、以下のコストがかかる。

• 既に置いてあるカードの間に置く時、両隣の数値の積のコストがかかる。
• 端に置く場合、1のコストがかかる。

1～Nのカードを置く時、総コストの期待値を求めよ。

解法

k番のカードを置く時のコストの期待値を順に求めて足して行こう。
k番のカードはコスト1で確定。以下2番以降のカードを置く場合を考える。

• 2/kの確率で両端になる。
• (k-2)/kの確率で、既存のカードの間に挟む。その際、1～(k-1)のカードのうち2枚に等確率()で挟まれる。(分母の2は左右どちらにどちらのカードが来るかを考慮する分)

よって上記のケースの和を取ればよい。
1～(k-1)のうちの2値の積の総和は二重ループで解いても良いが、式を工夫するとO(1)で書ける()

int N;
double R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	R=1;
	for(i=2;i<=N;i++) {
		R+=2.0/i;
		if(i>2) {
			double tot=((i-1)*i/2)*((i-1)*i/2)-(i-1)*i*(2*i-1)/6;
			tot/=(i-1)*(i-2);
			R+=tot*(i-2.0)/i;
		}
	}
	_P("%.12lf\n",R);
}

まとめ

Nの上限がえらい小さい…？