kmjp's blog

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

yukicoder : No.454 逆2乗和

yukicoder

すいませんゴリ押ししました。
http://yukicoder.me/problems/no/454

問題

非負実数Xが与えられる。
\displaystyle \sum_{n=1}^{\infty} \frac{1}{(X+n)^2}を求めよ。
誤差は10^-9まで許容される。

解法

\displaystyle A_n = \sum_{i=1}^{n} \frac{1}{(X+n)^2}とすると、真の解をAとしたとき \displaystyle \lim_{i \to \infty} A_i = Aとなる。
ここでA_nの真の解に対する誤差 \displaystyle A - A_n = \sum_{i=n+1}^{\infty} \frac{1}{(X+i)^2}を考える。
右辺はnの逆２乗に対する和なので、おおよそnに反比例することが予想される。
そのため、愚直にA_nを計算する場合n=10^9程度まで処理すれば誤差が10^-9以下になることが期待できる。

実際、1.2×10^9回ループするとこの問題はACできる。
ただ除算が重いため、除算を減らすよう若干の工夫が必要である。
というか自分はそれでゴリ押しした(ソース中コメント部参照)。

改めて \displaystyle A - A_n = \sum_{i=n+1}^{\infty} \frac{1}{(X+i)^2}を考える。
この総和の部分は、下記の通り２つの積分値で挟み込める。
\displaystyle \int_{t=n+1}^{\infty} \frac{1}{(X+t)^2} dt \lt \sum_{i=n+1}^{\infty} \frac{1}{(X+i)^2} \lt \int_{t=n}^{\infty} \frac{1}{(X+t)^2} dt

両端の積分を計算すると、以下のようになる。
\displaystyle \frac{1}{X+n+1} \lt \sum_{i=n+1}^{\infty} \frac{1}{(X+i)^2} \lt \frac{1}{X+n}
この時、両側の差は \displaystyle \frac{1}{X+n}-\frac{1}{X+n+1} = \frac{1}{(X+n)(X+n+1)}と大よそnの逆２乗に比例する。
よって、A_nの極限を求めるのではなく、A_n+1/(X+n)を求めれば、n=10^5程度までの計算で誤差が10^-9以下になる。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	double X;
	cin>>X;
	double ret=0;
	
	/*
	i=1200000000;
	X+=i;
	for(;i>=100;i-=3) {
		double a=(X*X);
		double b=(X-1)*(X-1);
		double c=(X-2)*(X-2);
		double ab=a*b;
		ret += (ab+c*(a+b))/(ab*c);
		X-=3;
	}
	for(;i>=1;i--) {
		ret += 1.0/(X*X);
		X--;
	}
	*/
	for(i=1;i<1000000;i++) {
		ret += 1/((X+i)*(X+i));
	}
	ret += 1/(X+i);
	
	_P("%.12lf\n",ret);
	
}

まとめ

本番ガンマ関数とか、SSEによる高速化とかいろいろ調べていたけど、結局ゴリ押し…。