mayoko’s diary

プロコンとかいろいろ。

SRM 494 div2 hard, div1 med:AlternatingLane

してやられた!という感じです。

解法

当然すべての場合を考えていると間に合わないので, 見方を変えます。

ランダムに選ばれた結果, 木の高さがそれぞれ h[0], h[1], ..., h[n-1] になったとします。
整数の組 (i, j) について, |h[j]-h[i]| という値が採用される条件は, 仮に h[i] < h[j] であるとすると,
h[i] < h[i+1], h[i+1] < h[i+2], ..., h[j-1] < h[j],
h[i-1] > h[i], h[j] > h[j+1]
が成り立つことです。この条件が成り立っていないと, まず一行目の場合は, h[i] から一回木の高さを下げて, そこから h[k] を採用することで, |h[j]-h[i]| より高いスコアを獲得できるので損です。また, 二行目の条件が成り立っていないと |h[i-1]-h[j+1]| の値を採用しないとスコアが損になります。

ということで, 以上 2 条件が成り立っている必要があります。ということで, 各 (i, j) の組について以上の条件を満たす |h[j]-h[i]| の期待値を求める…わけではありません。もうちょっと工夫できます。

上の条件が成り立っているということは, |h[j]-h[i]| は |h[i+1]-h[i]| + |h[i+2]-h[i+1]| + ... + |h[j]-h[j-1]| の和と同じです。つまり, いちいち上のように考えずに, 愚直に各 (i, i+1) について, |h[i+1]-h[i]| の期待値を求め, その和が答え, ということになります。

下のコードでは h[i+1] の高さで場合分けして頑張りました。

class AlternatingLane {
public:
    double expectedBeauty(vector <int> low, vector <int> high) {
        int n = low.size();
        double ret = 0;
        for (int i = 0; i < n-1; i++) {
            for (int j = low[i+1]; j <= high[i+1]; j++) {
                ll sum = 0;
                ll num = (high[i]-low[i]+1);
                if (j >= high[i]) {
                    sum += j*num;
                    sum -= (low[i]+high[i]) * num / 2;
                } else if (j <= low[i]) {
                    sum += (low[i]+high[i]) * num / 2;
                    sum -= num*j;
                } else {
                    sum += (ll)j * (j-low[i]+1);
                    sum -= (ll)(j+low[i]) * (j-low[i]+1)/2;
                    sum += (ll)(high[i]+j+1) * (high[i]-j)/2;
                    sum -= (ll)j*(high[i]-j);
                }
                ret += 1.*sum / (high[i]-low[i]+1) / (high[i+1]-low[i+1]+1);
            }
        }
        return ret;
    }
};