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