kmjp's blog

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

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枚に等確率( \displaystyle \frac{1}{2*{}_{k-1} C_2})で挟まれる。(分母の2は左右どちらにどちらのカードが来るかを考慮する分)

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

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の上限がえらい小さい…?

広告を非表示にする