torus711 のアレ

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

TopCoder SRM 577, Division 1, Level 1 : EllysRoomAssignmentsDiv1

概要

SRM のようにコンテスタントを部屋に振り分ける形式のコンテストをする。
部屋の数 R は、コンテスタントの数を N として R = N / 20 + ( N % 20 ? 1 : 0 ) となる。
部屋への割り振りは、コンテスタントのレートを用いて次のように決定される。

  • 割り当てが決定していないコンテスタントがいなくなるまで、以下の操作をする
    1. 残っているコンテスタントから、レートが高い順に R 人選ぶ
    2. 選ばれたコンテスタントをそれぞれ異なる部屋に割り振る

全てのコンテスタントのレートの情報が与えられ、最初のデータは Elly のレートである。
Elly の部屋の平均レートの期待値を求めよ。

解法

エリーがいる部屋に来るコンテスタントが確定している場合、単に全て足して人数で割ったものが答えになります。
この問題では誰が来るかが分からないので、部屋のレートの和を total として、R 人のグループ毎に次のように処理します。

  • R 人のグループにエリーがいる場合 : エリーのレートを total に足す
  • それ以外の場合 : そのグループのレートの平均を total に足す

全てのグループが R 人である場合には、total をグループの数(=部屋の人数)で割れば答えが求まります。
それ以外の場合、特別に処理する必要があります。

最後のグループにエリーがいれば、総和にエリーのレートを足し、部屋の人数を一人増やすだけです。
そうでないとき、グループの人数を n とするとそのグループからエリーの部屋に来る確率 p が n / R と求まります。
そうすると、部屋に来た場合の平均に部屋に来る確率を掛けたものと、部屋に来ない場合の平均に部屋に来ない確率を掛けたものを足しあわせた値が答えになります。
この値は、最後のグループを除いた場合の部屋の人数を count 、最後のグループの平均レートを ave とすると、
 \frac{total + ave}{count + 1}p + \frac{total}{count}( 1 - p )
となります。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef istringstream ISS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

class EllysRoomAssignmentsDiv1
{
public:
	double getAverage( vector <string> ratings )
	{
		VI rates;
		{
			string str = accumulate( ALL( ratings ), string() );
			ISS iss( str );
			int tmp;
			while ( iss >> tmp )
			{
				rates.PB( tmp );
			}
		}

		const int elly = rates[0];
		sort( ALL( rates ), greater<int>() );

		const int R = rates.size() / 20 + ( rates.size() % 20 ? 1 : 0 );
		VVI groups;
		while ( !rates.empty() )
		{
			int p = min( R, (int)rates.size() );
			groups.PB( VI( rates.begin(), rates.begin() + p ) );
			rates.erase( rates.begin(), rates.begin() + p );
		}
		
		double total = 0;
		int count = 0;
		REP( i, 0, groups.size() )
		{
			if ( groups[i].size() < R )
			{
				break;
			}

			if ( binary_search( ALL( groups[i] ), elly, greater<int>() ) )
			{
				total += elly;
			}
			else
			{
				total += accumulate( ALL( groups[i] ), 0. ) / groups[i].size();
			}
			count++;
		}

		VI last = groups.back();
		if ( last.size() < R )
		{
			if ( binary_search( ALL( last ), elly, greater<int>() ) )
			{
				total += elly;
				count++;
				return total / count;
			}
			else
			{
				double ave = accumulate( ALL( last ), 0. ) / last.size();
				double p = (double)last.size() / R;

				return ( ( total + ave ) / ( count + 1 ) ) * p + ( total / count ) * ( 1 - p ); 
			}
		}

		return total / count;
	}
};