Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2012-03-04SRM535 Div1

SRM535 Div1 250 FoxAndGCDLCM

| 17:26 | SRM535 Div1 250 FoxAndGCDLCM - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM535 Div1 250 FoxAndGCDLCM - SRM diary(Sigmar) SRM535 Div1 250 FoxAndGCDLCM - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うーん全然分からない

大真面目に素因数分解でもして解いてしまおう

ちょっと時間かかったけどできた

なぜか答えが合わない

(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

| 17:26 | SRM535 Div1 500 FoxAndBusiness - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM535 Div1 500 FoxAndBusiness - SRM diary(Sigmar) SRM535 Div1 500 FoxAndBusiness - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

難しすぎて解けなかった


後で

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