読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

SRM 656 Div1 Easy - RandomPancakeStack

SRM programming

問題

TopCoder Statistics - Problem Statement

問題概要

n枚のパンケーキがある。それらのパンケーキは0~n-1までの番号が振られており、i番目のパンケーキは大きさがi+1でおいしさがd_iである。パンケーキをいくつか選んでプレートにのせてタワー状のパンケーキを作ろうと思う。そのとき、以下の様な手順でプレートをつくる:

  1. まず、n枚の中からランダムに1枚パンケーキを選んでのせる。
  2. もう残っているパンケーキがなければ終了する。
  3. 残っているパンケーキの中からランダムに1枚のパンケーキを選ぶ。そして、選ばれたパンケーキの大きさが現在プレートにのっている一番上のパンケーキよりも大きいなら、そのパンケーキをのせずに操作を終了する。
  4. 選ばれたパンケーキをプレートの一番上にのせ、2.に戻る。

この操作を終了した時にプレートに乗っているパンケーキ全てのおいしさの合計をそのプレートのおいしさとする。今、d_0 , d_1, ... d_{n-1}が与えられるのでプレートのおいしさの期待値を求めよ。

  • 1 \le n \le 250
  • 1 \le d_i \le 1000

イデア

大きさが0のパンケーキが直感的にわかりにくいので問題ではi番目のパンケーキの大きさがi+1となっているが、別にiとして考えても特に差し支えは無いので、以下では大きさをそのように扱う。

i番目のパンケーキがプレートの一番上にある時に、それ以降の操作で得られるおいしさの合計の期待値を E[i ] とすると、はじめの1枚がランダムに選ばれることを考えれば求める答えは期待値の線形性より \displaystyle \sum_{i=0}^{n-1} ( \frac{1}{n} * (d[i ] + E[i ]) ) となる。以下では、 E[i ] を求めることについて考えよう。

プレートに今s枚のパンケーキがのっている時、残っているパンケーキはn-s枚である。次のパンケーキはこのn-s枚のうちのどれか1つから選ばれるわけであるが、ここで選ばれたパンケーキがプレートの一番上のパンケーキよりも大きいなら操作が終了する。ということは、この時はこれ以降の期待値は0になる。逆に、小さければパンケーキをプレートの一番上にのせて、その後も操作が続行していくことになる。つまりこの状態での期待値は、全ての正しい遷移jに対して d[j ] + E[(j 番目のパンケーキが一番上でプレート上にs+1枚ある) ] ものの合計をn-sで割ったものということになる。

つまり、ここまでのことをまとめるとEの情報として「今プレートの一番上にあるパンケーキの大きさw」と「プレート上にあるパンケーキの数s」が必要になるわけである。ここで、プレート上の状態全てを知る必要はない。なぜなら、この2つがわかっていればまずプレート上にwより小さいパンケーキがのっていることはあり得ないので0~w-1までのパンケーキはまだ残っていることがわかるからである。そしてその正しい遷移の期待値を足して割るためにsがあればよいということになる。

この期待値を E[w ][s ] と表すことにすれば、\displaystyle E[w ][s ] = \frac{1}{n-s} * \sum_{i=0}^{w-1} (d[i ] + E[i ][s+1 ]) ということになる。よって、このEを全て計算するためにはO(n^3)かかるが、n \le 250であることを考えれば十分である。

そして、この期待値の設定から、最終的に答えるべきものは E[n ][0 ] ということになる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

class RandomPancakeStack {
    public:
    double expectedDeliciousness(vector<int> d) {
        int n=d.size();
        double E[251][251]={0};

        for(int w=1; w<=n; ++w)rep(s,n)
        {
            rep(i,w) E[w][s] += d[i]+E[i][s+1];
            E[w][s]/=n-s;
        }

        return E[n][0];
    }
};