kmjp's blog

競技プログラミング参加記です

TopCoder SRM 629 Div2 Medium CandyMaking

550ptということでDiv2 Mediumにしてはちょっと難しめ。
http://community.topcoder.com/stat?c=problem_statement&pm=13340

問題

N人の生徒がそれぞれC[i]の容積の入れ物を持っており、W[i]の重さの飴を欲しがっている。
各生徒の容器に、ある密度の飴を入れることを考える。
この時、各生徒の不幸は入れ物いっぱいに入れた飴の重さとW[i]の差の絶対値となる。
不幸の総和が最小となるよう、密度を決めよ。

解法

密度をWとすると、不幸の総和は \sum_i |x*C_i - W_i|である。
個々の|x*C_i - W_i|は明らかに下に凸なので、それを重ねた上記総和も下に凸である。
よってWを三分探索で求めればよい。

class CandyMaking {
	public:
	int N;
	vector<int> V1,V2;
	double diff(double den) {
		double tot=0;
		int i;
		FOR(i,N) tot+=fabs(V2[i]-V1[i]*den);
		return tot;
	}
	
	double findSuitableDensity(vector <int> containerVolume, vector <int> desiredWeight) {
		N=containerVolume.size();
		V1=containerVolume;
		V2=desiredWeight;
		double L=1e9,R=1e-9;
		int i;
		FOR(i,N) L=min(L,1.0*V2[i]/V1[i]);
		FOR(i,N) R=max(R,1.0*V2[i]/V1[i]);
		
		FOR(i,100) {
			double M1=(L*2+R)/3;
			double M2=(L+R*2)/3;
			double D1=diff(M1),D2=diff(M2);
			if(D1<D2) R=M2;
			else if(D1>D2) L=M1;
			else L=M1,R=M2;
		}
		return diff((L+R)/2);
		
	}
}

まとめ

三分探索だから550ptなんだろうね。