Looksery Cup 2015 : H. Degenerate Matrix

本番は3番目とかなり早いタイミングで正解できました。
http://codeforces.com/contest/549/problem/H

問題

2*2の行列が与えられる。
行列の各要素を最大e以下増減させたとき、行列式を0に出来るような最小のeを求めよ。

解法

元の行列の行列式はである。
よってとが等しくなるようにeずらすことを考える。
eを二分探索で求めていこう。

各項が最大eだけずらせるとすると、前者は、後者はの範囲を取る。
よってこれらが共通部分を持つなら、行列式を0にできる。

ll A,B,C,D;

bool ok(double dif) {
	double ma1=-1e20,mi1=1e20;
	double ma2=-1e20,mi2=1e20;
	
	ma1=max(ma1,(A+dif)*(D+dif));
	ma1=max(ma1,(A+dif)*(D-dif));
	ma1=max(ma1,(A-dif)*(D+dif));
	ma1=max(ma1,(A-dif)*(D-dif));
	ma2=max(ma2,(C+dif)*(B+dif));
	ma2=max(ma2,(C+dif)*(B-dif));
	ma2=max(ma2,(C-dif)*(B+dif));
	ma2=max(ma2,(C-dif)*(B-dif));
	
	mi1=min(mi1,(A+dif)*(D+dif));
	mi1=min(mi1,(A+dif)*(D-dif));
	mi1=min(mi1,(A-dif)*(D+dif));
	mi1=min(mi1,(A-dif)*(D-dif));
	mi2=min(mi2,(C+dif)*(B+dif));
	mi2=min(mi2,(C+dif)*(B-dif));
	mi2=min(mi2,(C-dif)*(B+dif));
	mi2=min(mi2,(C-dif)*(B-dif));
	
	mi1=max(mi1,mi2);
	ma1=min(ma1,ma2);
	return mi1<=ma1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	double L=0,R=1e10;
	FOR(i,1000) {
		double M=(L+R)/2;
		if(ok(M)) R=M;
		else L=M;
	}
	_P("%.12lf\n",(L+R)/2);
}

まとめ

本番さっくり思いつけて良かった。