SRM 481 div1 med: BatchSystemRoulette

問題

TopCoder Statistics - Problem Statement

解法

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;
    }
};