メモ

yukicoderでゆるふわgolf

yukicoder No.352 カード並べ

問題はこちら
No.352 カード並べ - yukicoder

期待値の線形性から、kのカードを置くときのコストの期待値Xkをそれぞれ求め、それらを合計すれば良い
k=1,2のとき1となるのはあきらか
k≧3のカードを並べるとき、i,j＜kのカードが隣り合っている確率は2*(k-2)!/(k-1)!=2/(k-1)
（i,jをひとまとめにしてk-2要素を並べた後でi,jの順序を決める、と考える）
であり、更にこの時、この間にカードを置く確率は1/k
よって期待値は
\displaystyle{X_k=\sum_{1\leq i< j< k}\frac{2ij}{(k-1)k}+\frac{2}{k}}
ここで\sum_{1\leq i< j< k}ij=\frac{1}{2}((\sum_{i=1}^{k-1} i)^2-\sum_{i=1}^{k-1} i^2)=\frac{1}{24}(k-1)k(3 k^2-7k+2)なので
（1つ目の等号は九九表を思い浮かべれば分かる。2つ目は和の公式から）
X_k=\frac{1}{12}(3 k^2-7k+2)+\frac{2}{k}となる。ここまでわかればループして足せば良い

また、最後まで計算すれば
\begin{eqnarray*}2+\sum_{k=3}^n X_k&=&2+\frac{1}{12}(n-2)(n-1)(n+1)+2(H_n-H_2)\\&=&\frac{1}{12}(n-2)(n-1)(n+1)+2H_n-1\end{eqnarray*}
（ただしHは調和数）
という結果が得られる

int main(){
	int n,i;
	double s=2;
	//X1=X2=1の分は先に足しておく
	scanf("%d",&n);
	for(i=3;i<=n;i++)s+=(3*i*i-7*i+2)/12.0+2.0/i;
	printf("%f",s);
	return 0;
}

縮める
for(scanf("%d",&n);--n;)s+=X[n+1];
の形で書くことになるので、結局XnからX2までがたされることになる。
k≧3のときの式にk=2を代入すると1となるので、これはこのまま計算しても大丈夫
あとは事前にX1のぶんを足せば

n;
main(double s){
	for(s=scanf("%d",&n);--n;)s+=~-n*(3*n+2)/12.-2./~n;
	//3(n+1)^2-7(n+1)+2は(n-1)*(3n+2)と因数分解される
	n=!printf("%f",s);
}

87B