SRM494 Div1 Medium(500), Div2 Hard(1000) AlternatingLane

AlternatingLane

例えば木の高さが1,3,6,9,7,5だったとすると、高さが3,6,7の木を切り倒すので、美しさは単に隣り合う木の高さの差の和。それぞれの木の高さは独立だから、
Σ_1≦i≦n-1Σ_{low[i-1]≦j≦high[i-1]}Σ_{low[i]≦k≦high[i]}|j-k|/(high[i-1]-low[i-1]+1)/(high[i]-low[i]+1)
が答え。和の公式でループを１つ減らす。

#include <vector>
using namespace std;

class AlternatingLane{public:
double expectedBeauty( vector <int> low, vector <int> high )
{
    int n = (int)low.size();

    double ans = 0;

    for ( int i=1; i<n; i++ )
    {
        double t = 0;
        for ( int j=low[i-1]; j<=high[i-1]; j++ )
        {
            double l = low[i];
            double h = high[i];

            if ( h <= j )
                t += (j-(l+h)/2)*(h-l+1);
            else if ( l >= j)
                t -= (j-(l+h)/2)*(h-l+1);
            else
                t += (j-(l+j)/2)*(j-l+1),
                t -= (j-(j+h)/2)*(h-j+1);
        }

        ans += t / (high[i]-low[i]+1) / (high[i-1]-low[i-1]+1);
    }

    return ans;
}};