kmjp's blog

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

TopCoder SRM 733 Div1 Easy MinimizeAbsoluteDifferenceDiv1

Mediumが解けずレート減。
https://community.topcoder.com/stat?c=problem_statement&pm=14883

問題

5要素の整数列X[i]が与えられる。

X[a]/X[b]-X[c]/X[d] が最少となる(a,b,c,d)の組み合わせを求めよ。

解法

(a,b,c,d)の組み合わせは5!通りなので、全部列挙して値を比較すればよい。
分数の計算にdouble型を使うと精度不足で失敗するので、有理数表現を用いること。

bool cmp(pair<ll,ll> a,pair<ll,ll> b) {
	return (a.first*b.second<a.second*b.first);
	
}

class MinimizeAbsoluteDifferenceDiv1 {
	public:
	
	pair<ll,ll> val(ll a,ll b,ll c,ll d) {
		ll p=abs(a*d-b*c);
		ll q=b*d;
		ll g=__gcd(p,q);
		p/=g;
		q/=g;
		return {p,q};
		
	}
	
	vector <int> findTuple(vector <int> x) {
		int a,b,c,d;
		pair<pair<ll,ll>,vector<int>> V;
		pair<ll,ll> p={1000000,1};
		vector<int> R={5,5,5,5};
		FOR(a,5) FOR(b,5) FOR(c,5) FOR(d,5) {
			if(a==b) continue;
			if(a==c) continue;
			if(a==d) continue;
			if(b==c) continue;
			if(b==d) continue;
			if(c==d) continue;
			pair<ll,ll> v=val(x[a],x[b],x[c],x[d]);
			vector<int> A={a,b,c,d};
			if(v==p) R=min(R,A);
			if(cmp(v,p)) R=A, p=v;
		}
		
		return R;
		
	}
}

まとめ

いまいち主旨のわからない問題。