kmjp's blog

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

yukicoder : No.1539 不可欠な部分

yukicoder

これまた数学問。
https://yukicoder.me/problems/no/1539

問題

正整数Nが与えられる。
\displaystyle \int_0^{\frac{1}{e\pi^2}} e^{\cos \frac{x}{N}}\ dxの値を誤差10^-8以下で求めよ。

解法

下記シンプソンの近似公式を使う。
\displaystyle \quad \int_a^b f(x) dx \approx \frac{b-a}{6} \left \{ f(a) + 4 f \left( \frac{a+b}{2} \right) + f(b) \right \}

元の式にこれを適用すると
\displaystyle \int_0^{\frac{1}{e\pi^2}} e^{\cos \frac{x}{N}}\ dx \approx \frac{1}{6e\pi^2}\left(e + 4e^{\cos \frac{1}{2Ne\pi^2}} + e^{\cos\frac{1}{Ne\pi^2}}\right)
になるので右辺を求めればよい。

誤差が十分小さくなることの確認についてはEditorial参照。

int T;
int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	double pi=atan(1)*4;
	
	cin>>T;
	while(T--) {
		cin>>N;
		double d=1.0/(N*exp(1)*pi*pi);
		double a=exp(1)+4*exp(cos(0.5*d))+exp(cos(d));
		a/=(6.0*exp(1)*pi*pi);
		_P("%.12lf\n",a);
	}
}

まとめ

近似しよう、まではまだしも、これで誤差が許容範囲内かどうか確認するのは大変。