解いた問題のソースコードと解説など。


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!