TopCoder SRM 722 Div1 Medium MulticoreProcessing、Div2 Hard MulticoreProcessingEasy

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=14732
https://community.topcoder.com/stat?c=problem_statement&pm=14699

問題

いくつかのPCがあり、i台目のPCのコア数はC[i]、1コアあたり1秒で処理できる処理量をS[i]とする。

全部でJの処理を行うことを考える。
どれか１台のPCで処理するが、その際使用するコア数は1～C[i]で選択できるとする。
なお、コア数1からコア数を増やすごとにPの時間のペナルティがかかるとする。

最適なPC・コア数を選んだ時、処理を終える最短時間はどの程度か。

解法

各PCはどれか1台しか選ばないので、各PCにおける最短時間を求めればよい。

コア数をcとしたとき、かかる時間はceil(J/(S[i]*c))+(c-1)*Pとなる。
ceilを除けば、この値はコア数に対し下に凸となるので、基本的に３分探索でよい。
ただし切り上げが入るため誤差を考慮してちょっと余分に探索しておくとよい。

なお、P==0の場合コア数は最大なのが最適なのでその点は注意。

class MulticoreProcessing {
	public:
	ll hoge(ll J,ll P,ll S,ll C) {
		ll mi=1LL<<60;
		J=(J+S-1)/S;
		ll L=1;
		ll R=C;
		if(P==0) {
			L=R=C;
		}
		else {
			while(R-L>=10) {
				ll m1=(L*2+R)/3;
				ll m2=(L+R*2)/3;
				ll v1=(m1-1)*P+(J+m1-1)/m1;
				ll v2=(m2-1)*P+(J+m2-1)/m2;
				mi=min({mi,v1,v2});
				if(v1<v2) R=m2;
				if(v1>v2) L=m1;
				if(v1==v2) L=m1,R=m2;
			}
		}
		for(ll i=max(1LL,L-100000);i<=min(C,R+100000);i++) {
			mi=min(mi,(i-1)*P+(J+i-1)/i);
		}
		
		return mi;
		
	}
	
	long long fastestTime(long long jobLength, int corePenalty, vector <int> speed, vector <int> cores) {
		ll mi=1LL<<60;
		int i;
		FOR(i,cores.size()) mi=min(mi,hoge(jobLength,corePenalty,speed[i],cores[i]));
		return mi;
	}
}

まとめ

こういう切り上げ切り捨てが混ざる二分探索・三分探索苦手…。