SRM 656 Div2 Medium RandomPancakeStackDiv2

問題

SRM 656 - TopCoder Wiki

パンケーキが並んでいて,i番目のパンケーキは(i+1)の幅があり, その美味しさはd[i]で表される. これらのパンケーキを以下の手順で選んでいったとき, 選んだパンケーキの美味しさの総和の平均を求める問題.

  • パンケーキがない場合終了
  • ランダムに1つ選ぶ
  • 選んだパンケーキがスタックのトップのパンケーキの幅より多きければ選ばずに終了
  • 選んだパンケーキをスタックに詰む.
  • ステップ1に戻る.

解答

入力サイズは10なので,全ての選び方を考えても10!と小さい. 全探索を行いシミュレーションして求める.

class RandomPancakeStackDiv2
{
public:
  vector<bool> used;
  vector<int> deli;
  int n;
  double calc(double sumcost, int topsize) {
    // cout << "topsize=" <<topsize << " sumcost=" << sumcost << endl;
    int m = 0;
    double new_sumcost = 0;
    for (int i = 0; i < n; i++) if (!used[i]) m++;
    if (m == 0) return sumcost;
    for (int i = 0; i < n; i++) {
      if (used[i]) continue;
      used[i] = true;
      if ((i+1) < topsize) new_sumcost += calc(sumcost + deli[i], i+1) / m;
      else new_sumcost += sumcost / m;
      used[i] = false;
    }
    return new_sumcost;
  }
  double expectedDeliciousness(vector <int> d)
    {
      deli = d;
      n = d.size();
      used = vector<bool> (n, false);
      return calc(0, 2*n);
    }
};