torus711 のアレ

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

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

問題概要

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

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

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

解法

 Division 2, Level 2 の制約違いです.こちらの制約では,もはや順列の列挙はできません.別の方法を考える必要があります.
 Division 2, Level 2 に於いて順列を列挙して答えを求めた方法をよく観察してみます.順列を 1 つ固定したとき,そのとき使われるパンケーキの美味しさの和を求め, \frac 1 { N! } を掛けていました.定数を掛けているので和の部分をバラし,使われる各パンケーキの美味しさに \frac 1 { N! } を掛けてから足し上げるようにしても値は変わりません.また,あるパンケーキが答えに寄与する回数を c とすると,全順列に関して和をとったとき,そのパンケーキの美味しさにかかっている係数は \frac c { N! } です.この値は,このパンケーキが使われる確率に他なりません.従って,各パンケーキが使われる確率を求め,その値と美味しさの積の和をとれば答えが求まります.
 では,それぞれのパンケーキが使われる確率はどのように求まるでしょうか? いくつかのパンケーキを積み上げている状態があったとします.その状態から次に使えるパンケーキは,山の一番上のパンケーキより小さいものの内 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 の状態数が O( N^2 ) あり,各状態からの繊維が O( N ) 通りあるので,この DP に O( N^2 ) 時間かかります.答えの計算は O( N^2 ) 時間なので,全体の実行は O( N^3 ) 時間となります.

コード

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