Hatena::Grouptopcoder

tsubosakaの日記

2010-10-27

SRM 486 500

02:09

終了2分後に式があった。

i番目の要素とj番目の要素を考えたときにこれらのどちらかがpivotとして選ばれ、もう一方が逆側に移動する確率はL[i] > L[j]のとき2 / |k : L[i] <= L[k] && L[k] <= L[j]|となる、期待値の線形性を利用してあとは足すだけ

  public double getEval(int[] L) {
    double expected = 0.0;
    for(int i = 0 ; i < L.length ; ++i){
      for(int j = i + 1 ; j < L.length ; ++j){
        if(L[i] <= L[j])continue;        
        int cnt = 0;
        for(int k = 0 ; k < L.length ; ++k)
          if(L[j] <= L[k] && L[k] <= L[i])
            ++cnt;        
        expected += 2.0 / cnt; 
      }
    }
    return expected;
  }