SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。
2012-03-04SRM535 Div1
SRM535 Div1 250 FoxAndGCDLCM
コーディングフェーズ
うーん全然分からない
大真面目に素因数分解でもして解いてしまおう
ちょっと時間かかったけどできた
なぜか答えが合わない
(20分くらい悩み続ける)
LとGが途中から逆になってた。なんだそりゃ。終わってすぎる。。
提出
後で
冷静になって考えれば、L/Gをうまく2分割すればいいだけだった
L/Gの約数をiとして、gcd(i, L/G/i)==1となる場合だけ、i*G+L/G/i*Gを解の候補とする
もしgcd(i, L/G/i)!=1とすると、GCDがGでなくなるばかりかLCMもLでなくなるはずである
ソースコード
提出したひどい解法
vector <pair <ll, int> > factorp(ll n) { vector <pair <ll, int> > f; for(ll i=2; i*i<=n; i++) { int cnt=0; while(n%i==0) { n/=i; cnt++; } if(cnt>0) f.push_back(make_pair(i, cnt)); } if(n>1) f.push_back(make_pair(n, 1)); return f; } class FoxAndGCDLCM { public: long long get(long long G, long long L) { long long res; if(L<G) return -1; if(L%G!=0) return -1; res=L+G; vector <pair <ll, int> > lf, gf; lf=factorp(L); gf=factorp(G); for(ll i=1; i*i<=L; i++) { if(L%i!=0) continue; ll ii=i; for(int s=0; s<2; s++) { if(ii%G!=0) { ii=L/ii; continue; } vector <pair <ll, int> > f=factorp(ii); ll pp=1; vector <ll> done; for(int j=0; j<(int)lf.size(); j++) { bool ok=false; for(int k=0; k<(int)f.size(); k++) { if(lf[j].first==f[k].first && lf[j].second==f[k].second) ok=true; } if(!ok) { for(int k=0; k<lf[j].second; k++) pp*=lf[j].first; done.push_back(lf[j].first); } } for(int j=0; j<(int)gf.size(); j++) { bool ok=false; for(int k=0; k<(int)done.size(); k++) { if(gf[j].first==done[k]) ok=true; } if(!ok) { for(int k=0; k<gf[j].second; k++) pp*=gf[j].first; } } res=min(res, ii+pp); ii=L/ii; } } return res; } };
もっと頭のいい解法
ll gcd(ll a, ll b) { while(b) { a=a%b; swap(a, b); } return a; } class FoxAndGCDLCM { public: long long get(long long G, long long L) { long long res; if(L%G!=0) return -1; ll d=L/G; res=L+G; for(ll i=1; i*i<=d; i++) { if(d%i!=0) continue; if(gcd(i, d/i)!=1) continue; res=min(res, G*(i+d/i)); } return res; } };
SRM535 Div1 500 FoxAndBusiness
コーディングフェーズ
難しすぎて解けなかった
後で
ACRush氏の解を見て理解した
求めたいamountは、
- 社員iの給料:totalWork*(a[i]/(a[α]+a[β]+...))*p[i]
- 社員全員の給料:totalWork*( (a[α]*p[α]+a[β]*p[β]+...)/(a[α]+a[β]+...) )
- レンタル料:totalWork*K/(a[α]+a[β]+...)*3600
ここでa[α]+a[β]+...は、amountを最小にするK個のaの要素
給料+レンタル料はtotalWorkでくくり出せるので、amount/totalWorkをMと置く
M以下で仕事を終えられるようなa[α]、a[β]、...の選び方があるか判定できれば、2分探索ができる
Mは社員全員の給料とレンタル料の合計をtotalWorkで割った値以上であるので、
M>=(K*3600+a[α]*p[α]+a[β]*p[β]+...)/(a[α]+a[β]+...)
M*(a[α]+a[β]+...)>=K*3600+a[α]*p[α]+a[β]*p[β]+...
(M-p[α])*a[α]+(M-p[β])*a[β]+...>=K*3600
であるから、あるK人を選んだときに、(M-p[α])*a[α]+...がK*3600以上であれば、コスト的には足りるということになる
(M-p[α])*a[α]は単に大きい順にK個とれば、最大化できる
これで2分探索の判定が可能になる
ソースコード
class FoxAndBusiness { public: double minimumCost(int K, int totalWork, vector <int> a, vector <int> p) { double res; int n=a.size(); double hi=1e30, lo=0, mid; for(int t=0; t<1000; t++) { mid=(hi+lo)/2; vector <double> cand; for(int i=0; i<n; i++) { cand.push_back(a[i]*(mid-p[i])); } sort(cand.begin(), cand.end(), greater <double>()); double sum=accumulate(cand.begin(), cand.begin()+K, 0.); if(sum>=3600.*K) hi=mid; else lo=mid; } res=mid*totalWork; return res; } };
コメントを書く
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120304