SRM722 Lv2 : MulticoreProcessing
作成日：2017.10.13
最終更新日：2017.10.13
問題概要
$jobLength$単位の作業を$n$個ある並列処理システムのうちの一つで行う。
各システムは、$1$msに$speed$単位の作業を処理できるコアが$cores$個ある。
システム中のコアをすべて使う必要はないが、オーバーヘッドのため(使ったコアの個数$-1$)$\times$$corePenalty$msだけ余分に時間がかかる。
なるべく早く作業を終わらせる時にかかる時間をms単位で答えよ。
制約
$1 \leq jobLength \leq 10^18$
$0 \leq corePenalty \leq 10^9$
$1 \leq n \leq 50$
$1 \leq speed , cores \leq 10^9$
考え方
コアを$c$個使う時にかかる時間は$\frac{jobLength}{speed*c}$$+corePenalty*(c-1)$msである。
この式の第一項及び第二項はそれぞれ$c$に関して単調減少、単調増加であるから全体としては下に凸な$c$についての関数である。
よって、三分探索によってこの式の最小値を求めることができる。
この最小値を各システムごとに求めて、それらの最小値が答えである。
ソースコード
マクロ等はこちら
class MulticoreProcessing {
LL L,P;
bool eval(LL c , LL s){
long double x = (long double)L / s / c + P * (c-1);
long double y = (long double)L / s / (c+1) + P * c;
return x > y;
}
LL BS(LL a , LL b , LL s){
if(a-b<2) return a;
LL c = (a+b)/2;
return eval(c,s) ? BS(a,c,s) : BS(c,b,s);
}
public:
long long fastestTime(long long jobLength, int corePenalty, vector<int> speed, vector<int> cores) {
L = jobLength; P = corePenalty;
LL ans = L;
repp(i,0,speed.size()){
LL s = speed[i];
LL z = BS(cores[i],0,s);
ans = min(ans , (L+s*z-1) / (s*z) + P * (z-1));
}
return ans;
}
};解法まとめ
使うコアの数$c$において$\frac{jobLength}{speed*c}$$+corePenalty*(c-1)$を最小化するものを三分探索で求める。
但し上記コードでは、三分探索の代わりに差分の正負を見る二分探索を行っている。(3-13行)
この最小値を各システムについて求め、それらの最小値が答えである。(17-23行)