TopCoder, Single Round Match 656, Division 2, Level 2 : RandomPancakeStackDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13749&rd=16416

問題概要

　 枚のパンケーキがあって， 番のパンケーキの大きさは ，美味しさは である．
　このパンケーキ群を，以下の手順で積み上げる

1. ランダムに 1 枚のパンケーキを選び，皿に載せる
2. パンケーキが残っている間，以下の手順を繰り返す
   1. 残っているパンケーキから 1 枚をランダムに選ぶ
   2. 選んだパンケーキが，積み上げられたパンケーキの一番上のものより大きいなら手順を終了する
   3. 選んだパンケーキを，積み上げられたパンケーキの一番上に載せる

　積み上げられたパンケーキの美味しさを，使われたパンケーキの美味しさの和であると定義する．上記手順で積み上げられるパンケーキの美味しさの期待値を求めよ．
　

解法

　期待値の定義通り，事象に対応する値とその事象の発生確率の積の和を求めます．
　パンケーキを積もうとする順序は大きさ の順列で表され， 通りあります．またその全てが等しい確率 で発生します．そのそれぞれから得られる美味しさを計算して， を掛けたものを足し上げれば，問題を解くことができます（もちろん， は後から（ の外から）掛けてもよいです）．順列の列挙には std::next_permutation を使うと便利です．
　調べなければならない順列の総数が 通りあり，1 つの順列から得られる美味しさの計算に 時間掛かります．従って，全体では の時間がかかります．

コード

using VPII = vector< pair< int, int > >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define EB emplace_back

#define fst first
#define snd second

class RandomPancakeStackDiv2
{
public:
	double expectedDeliciousness( vector <int> d )
	{
		const int N = SZ( d );

		VPII cakes;
		REP( i, N )
		{
			cakes.EB( i, d[i] );
		}

		double p = 1;
		REP( i, N )
		{
			p /= i + 1;
		}

		double res = 0;
		do
		{
			int score = 0, last = 11;
			FOR( cake, cakes )
			{
				if ( last < cake.fst )
				{
					break;
				}
				last = cake.fst;
				score += cake.snd;
			}

			res += score * p;
		}
		while ( next_permutation( ALL( cakes ) ) );

		return res;
	}
};