TopCoder, Single Round Match 656, Division 1, Level 1 : RandomPancakeStack

問題文

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

問題概要

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

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

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

解法

　Division 2, Level 2 の制約違いです．こちらの制約では，もはや順列の列挙はできません．別の方法を考える必要があります．
　Division 2, Level 2 に於いて順列を列挙して答えを求めた方法をよく観察してみます．順列を 1 つ固定したとき，そのとき使われるパンケーキの美味しさの和を求め， を掛けていました．定数を掛けているので和の部分をバラし，使われる各パンケーキの美味しさに を掛けてから足し上げるようにしても値は変わりません．また，あるパンケーキが答えに寄与する回数を とすると，全順列に関して和をとったとき，そのパンケーキの美味しさにかかっている係数は です．この値は，このパンケーキが使われる確率に他なりません．従って，各パンケーキが使われる確率を求め，その値と美味しさの積の和をとれば答えが求まります．
　では，それぞれのパンケーキが使われる確率はどのように求まるでしょうか？　いくつかのパンケーキを積み上げている状態があったとします．その状態から次に使えるパンケーキは，山の一番上のパンケーキより小さいものの内 1 つであり，また，そのそれぞれが使われる確率を求めるには残っているパンケーキの個数を知る必要がます．つまり「いつかのパンケーキが積まれた状態である」という情報からは計算できません．逆に，積んだ個数と一番上のパンケーキが分かっていれば確率を計算できますし，次の状態でのパンケーキの数及び一番上のパンケーキももちろん分かります．ここから，次のような動的計画法を考えることができます．

• dp[ 使ったパンケーキの数 ][ 最後に使ったパンケーキの番号 ] := 確率

初期状態として，dp[ 0 ][ N ] のみ 1 で，それ以外は 0 としておきます（N は対応するパンケーキが存在しない状態をいい感じに扱うための値です）．dp[ i ][ j ] という状態からの遷移を考えてみると，次に使える各パンケーキ k ( k < j ) に対して

• dp[ i + 1 ][ k ] += dp[ i ][ j ] / ( N - i )

という更新をすることになります．右辺にある ( N - i ) は残っているパンケーキの数であり，1 / ( N - i ) はある特定のパンケーキが選択される確率です．この計算が終わったあと，各 i, j に対して dp[ i ][ j ] * d[j] を計算して足し上げれば答えが求まります．
　DP の状態数が あり，各状態からの繊維が 通りあるので，この DP に 時間かかります．答えの計算は 時間なので，全体の実行は 時間となります．

コード

#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 ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )

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

double dp[ 256 ][ 256 ];

class RandomPancakeStack
{
public:
	double expectedDeliciousness( vector <int> d )
	{
		{ // init for local test
			fill( AALL( dp, double ), 0 );
		}

		const int N = SZ( d );
		dp[0][N] = 1;
		// dp[ 食べた数 ][ 最後に食べたパンケーキ ] := 確率

		REP( i, N )
		{
			REP( j, N + 1 )
			{
				REP( k, j )
				{
					dp[ i + 1 ][k] += dp[i][j] / ( N - i );
				}
			}
		}

		double res = 0;
		REP( i, N + 1 )
		{
			REP( j, N )
			{
				res += dp[i][j] * d[j];
			}
		}
		return res;
	}
};