torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

 N 枚のパンケーキがあって,i 番のパンケーキの大きさは i + 1 ,美味しさは d_i である.
 このパンケーキ群を,以下の手順で積み上げる

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

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

解法

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

コード

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;
	}
};