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; } }
まとめ
いまいち主旨のわからない問題。