SRM 494 Div2 Hard AlternatingLane
やりかた
木の高さはそれぞれ独立なので、隣合う木の高さの差の期待値を足していけばいい。独立なら和の期待値は期待値の和。
以下ソース。
class AlternatingLane { public: double sum(int a, int l, int h){ if(h <= a) return (a - (l + h) / 2.0) * (h - l + 1); if(a <= l) return ((l + h) / 2.0 - a) * (h - l + 1); return (h - a) / 2.0 * (h - a + 1) + (a - l) / 2.0 * (a - l + 1); } double expectedBeauty(vector <int> low, vector <int> high) { int N = low.size(); double ans = 0.0; for(int i = 1; i < N; i++){ double t = 0; for(int j = low[i - 1]; j <= high[i - 1]; j++) t += sum(j, low[i], high[i]); ans += t / (high[i] - low[i] + 1) / (high[i - 1] - low[i - 1] + 1); } return ans; } };
Div2Hardはもう一周するつもりなのでそのときにもろもろちゃんと書く。いまは疲れきってるので略。
Get up! 明日のSUPER ST@R!