yukicoder No.454 逆2乗和

実験しながら適当に投げたら通ってしまった

愚直でいけたり？→n=10^9近くまで計算しないとダメっぽい
n=10^7くらいまでで様子見→サンプルに関しては10^-7を足せばちょうどいい感じ
じゃあとりあえずそれを投げてみる→通っちゃった……

ちゃんと考察
適当な項まで足して、残りは誤差項として適当におさえてしまいたい。
誤差項の評価にいい感じの優級数や劣級数は思いつかないのでとりあえず積分で殴ってみる
1/(x+t)^2はtについて単調減少関数であることから
$\displaystyle{ \sum_{n=N+1}^{\infty}\frac{1}{(x+n)^{2}}<\int_{N+1}^{\infty}\frac{1}{(x+t-1)^{2}}dt=\frac{1}{x+N}\\ \sum_{n=N+1}^{\infty}\frac{1}{(x+n)^{2}}>\int_{N+1}^{\infty}\frac{1}{(x+t)^{2}}dt=\frac{1}{x+N+1}}$
が成立する
（「調和級数　積分」などでググると似たような評価をやってる分かりやすい図が出てくる）
ということで、「第N項まで計算したら、誤差は1/(x+N)くらい」という事がわかる
実際に「第N項までの和に1/(x+N)を足したもの」と真値の差を評価すると
$\displaystyle{ 0<((\sum_{n=1}^{N}\frac{1}{(x+n)^{2}})+\frac{1}{x+N})-\sum_{n=1}^{\infty}\frac{1}{(x+n)^{2}}\\ <((\sum_{n=1}^{N}\frac{1}{(x+n)^{2}})+\frac{1}{x+N})-((\sum_{n=1}^{N}\frac{1}{(x+n)^{2}})+\frac{1}{x+N+1})\\ =\frac{1}{(x+N)(x+N+1)}}$
となるので、例えばN=10^5くらいまで計算すれば要求される精度を得られる

#define N 1000000
int main(){
	double x,s=0;
	int n;
	scanf("%lf",&x);
	for(n=1;n<=N;n++)s+=1/(x+n)/(x+n);
	printf("%.9f",s+1/(x+N));
	return 0;
}

適当に縮める

double s,n;
i;
main(){
	for(scanf("%lf",&n);n++<1e7;)s+=1/n/n;
	i=!printf("%.9f",s+1/n);
}

83B

メモ

yukicoderでゆるふわgolf

yukicoder No.454 逆2乗和