SubarrayAverages [2018 TCO Algorithm Round 2B Div1 Easy]

http://community.topcoder.com/stat?c=problem_statement&pm=14936

N要素の数列arrがある。
これに以下の操作を0回以上行って作ることのできる、辞書順最小の数列を答えよ。
「連続する部分列について、平均を取って全ての要素を平均に置き換える」

解法

辞書順最小の構築問題には典型がある。
「先頭から貪欲に辞書順小さくなるように構築する」
先頭から作っていくが、左端は決まっているので、右端を全探索する。
その中で最も平均が小さい要素で操作を行えばいい。

struct SubarrayAverages {
    vector<double> findBest(vector<int> arr) {
        int n = arr.size();
        vector<double> ans(n);
        rep(i, 0, n) ans[i] = arr[i];

        rep(L, 0, n) {
            double mi = 1e9;
            int mi_R = -1;

            double sm = 0;
            int cnt = 0;
            rep(R, L, n) {
                sm += ans[R];
                cnt++;

                if (sm / cnt < mi) {
                    mi = sm / cnt;
                    mi_R = R;
                }
            }

            rep(i, L, mi_R + 1) ans[i] = mi;
        }

        return ans;
    }
};