Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-04SRM535 Div1

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