トリッキー問題コンテスト : B - 一変数方程式

言語による差も結構出る問題。
http://tricky.contest.atcoder.jp/tasks/tricky_2

問題

xに関する方程式ax^2+bx+c=0の解を答えよ。
なお-2^31<= a,b,c < 2^31である。

解法

この問題の注意点の1つはa,b,c=0の時の処理で、もう一つは精度である。
まず、a,bが0かどうかにより方程式が0次・1次・2次のいずれになるか変わる。

• 0次式の時：c==0なら答えは無限にあり、c!=0なら解なし
• 1次式の時：x=-c/bが答え
• 2次式の時：2次方程式の解の公式を使うだけ

最後の2次式では精度が問題となる。
10^-9≒2^-30程度の精度が求められるが、2次方程式では計算中に平方根を含むため、その前段階で2^-60程度の精度を保持する必要がある。
仮数53bitの普通のdouble型ではこの精度は保てないので、80bitのlong double(仮数64bit)を使うとよい。

void solve() {
	int f,i,j,k,l,x,y,loop;
	int T;
	cin>>T;
	FOR(loop,T) {
		ll A,B,C;
		scanf("%lld%lld%lld",&A,&B,&C);
		__float80 aa=A,bb=B,cc=C;
		if(A==0 && B==0) _P("%d\n",(C==0)?3:0);
		else if(A==0 && B!=0) _P("1 %.12Lf\n",-cc/bb);
		else {
			__float80 d=bb*bb-4*aa*cc;
			if(d<-1e-9) _P("0\n");
			else if(d<=1e-9) _P("1 %.12Lf\n",-bb/(2*aa));
			else {
				d=sqrt(d);
				__float80 d1=(-bb+d)/(2*aa),d2=(-bb-d)/(2*aa);
				_P("2 %.12Lf %.12Lf\n",min(d1,d2),max(d1,d2));
			}
		}
	}
}

まとめ

本番まさかと思って80bit小数使って成功したのでびっくり。
一応事前に分子分母を少し割ったりして精度を保つ手法もあるようだが…。