メモ

yukicoderでゆるふわgolf

yukicoder No.553 AlphaCoder Rating

問題はこちら
No.553 AlphaCoder Rating - yukicoder

ほとんどそのまま数式を計算すればよいが、g^(-1)とF(∞)だけは非自明。
gの逆関数はにぶたんで、F(∞)は適当に大きなxを用いてF(x)で近似することで、問題文の数式をそのまま実装して答えを得ることもできる。
以下では数学をやる解法を説明する。

g^(-1)(x)=800*log2(x)は明らか。
F(∞)については等比級数の和の公式
\sum_{i=1}^\infty r^i=\frac{r}{1-r}を用いて
F(\infty)=\dfrac{\sqrt{\frac{0.81}{1-0.81}}}{\frac{0.9}{1-0.9}}=\frac{1}{\sqrt{19}}が得られる

あとは、項を0.9倍ずつしながら足すという方法により、powを使うこと無く計算できる

n,t;
double r,de,nu,co,Fn,fn;
main(){
	scanf("%d",&n);
	r=0.9;
	while(n--){
		scanf("%d",&t);
		de+=r;
		nu+=r*pow(2,t/8e2);
		co+=r*r;
		r*=0.9;
	}
	Fn=sqrt(co)/de;
	fn=1200*(Fn-1/sqrt(19))/(1-1/sqrt(19));//F(1)=1
	printf("%.f",800*log2(nu/de)-fn);
}


このコードを基本にしつつ、nの読み飛ばしを工夫したり、f(n)を求める際の定数をいい感じにくくりだす事によって次が得られる

t;
float r,d,n,c;
main(i){
	for(;~scanf("%d",&t);r=--i?r:1)d+=r*=.9,c+=r*r,n+=r*pow(2,t/8e2);
	printf("%f",800*log2(n/d)+358-1557*sqrt(c)/d);
	//1557≒1200/(1-1/√19)、358≒1557/√19
}

136B
さて、ここでループ終了時にrに入っている値が0.9^nであることに注意しよう。
\sum_{i=1}^n 0.9^i=9*(1-0.9^n)
\sum_{i=1}^n 0.81^i=81/19*(1-0.81^n)
であることから、d=9*(1-r)、c=81/19*(1-r*r)であり、d,cの値はrから導出することもできる事がわかる
実際には、dは計算した方がよく、cはrから求めたほうが短くなる

t;
float r,n,d;
main(i){
	for(;~scanf("%d",&t);r=--i?r:1)d+=r*=.9,n+=r*pow(2,t/8e2);
	printf("%f",800*log2(n/d)+357-3213*sqrt(1-r*r)/d);
}

131B