SRM diary(Sigmar)

SRM535 Div1 250 FoxAndGCDLCM

SRM535, Div1 | 17:26 |

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

SRM535, Div1 | 17:26 |

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;
	}
};