SRM 481 div1 med: BatchSystemRoulette
解法
div2 hard と同じく, 各ユーザーごとに, 合計時間が短いやつ順に並べるのが最適です。
mayokoex.hatenablog.com
- 合計時間ごとに並べるので, あるユーザー u が使いたい合計時間 total 未満で処理が終わるユーザーまでにかかる時間 sum は u に必ずかかる。
- で, total だけ合計時間がかかるユーザーが size 人いたとすると, どのユーザーから順番にやっていくかはランダムなので, (size-1)/2 番目になるというのが平均になる。
- つまり, ユーザー u のタスクの処理をはじめるまでにかかる平均時間は sum + total*(size-1)/2
- ユーザー u がやりたいタスクそれぞれの順番はどうやっても変わらないので, これは完全にランダムに決まる
- タスク i の前にタスク j をやるか/やらないかは確率 1/2 で, これらの事象は他のタスクとの順番と独立なので, タスク i を始めるまでにかかる時間の期待値は, 0.5 * (total - task[i]) (task[i] は タスク i の処理時間)
これらのことを考慮してコードを組めばよいです。
map を使いまくったよくわからないコードになっています。
class BatchSystemRoulette { public: vector <double> expectedFinishTimes(vector <int> duration, vector <string> user) { map<string, vector<pii> > mp; int n = duration.size(); for (int i = 0; i < n; i++) { mp[user[i]].emplace_back(duration[i], i); } map<ll, vector<vector<pii> > > mpp; for (auto p : mp) { ll sum = 0; for (pii el : p.second) sum += el.first; mpp[sum].push_back(p.second); } vector<double> ret(n); ll sum = 0; for (auto p : mpp) { ll size = p.second.size(); double average = 0.5*(size-1)*p.first + sum; for (vector<pii> pp : p.second) { ll total = 0; for (pii pr : pp) { total += pr.first; } for (pii pr : pp) { ll other = total-pr.first; ret[pr.second] = 0.5*other+average + pr.first; } } sum += p.first*size; } return ret; } };