mayoko’s diary

プロコンとかいろいろ。

SRM 536 div1 easy: MergersDivOne

解法

先に併合されるものほど, 影響が小さくなります。よって, 以下のような解法で解けます。

まず小さい順にソートして, dp をします。dp[i] = (i 番目までで得られる平均値の最大値) とすると, dp[i] は,

  • dp[0] = revenue[0]
  • dp[k] = max( (dp[i]+revenue[i+1]+...+revenue[k])/(k-i+1) ) (i = 0, 1, ..., k-1)

で出来ます。
公式 editorial 見たら「全部 2 つで平均取るのが良い」って書いてあって確かにそっちのほうが簡潔なんですが, こっちのほうが何も考えないで出来て僕は安心できます。

double dp[55];
double INF = 1e9;

class MergersDivOne {
public:
    double findMaximum(vector <int> revenues) {
        int n = revenues.size();
        sort(revenues.begin(), revenues.end());
        for (int i = 0; i <= n; i++) dp[i] = -INF;
        dp[0] = revenues[0];
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                double average = dp[i];
                for (int k = i+1; k <= j; k++) average += revenues[k];
                average /= j-i+1;
                dp[j] = max(dp[j], average);
            }
        }
        return dp[n-1];
    }
};