TopCoder SRM 577, Division 2, Level 2 : EllysRoomAssignmentsDiv2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12521&rd=15497

概要

Division 1, Level 1 とほぼ同じ。
最もレートが高いコンテスタントがいる部屋にエリーが割り当てられる確率を求めよ。

解法

エリーのレートによって以下の三通りに分けられます。

• エリーのレートが一番高い -> 1
• そうではなく、エリーのレートが上から R 以内 -> 0
• それ以外 -> 1 / R

コード

typedef vector<int> VI;
typedef istringstream ISS;

#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

class EllysRoomAssignmentsDiv2
{
public:
	double getProbability( 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];
		if ( elly == *max_element( ALL( rates ) ) )
		{
			return 1;
		}
		
		const int R = rates.size() / 20 + ( rates.size() % 20 ? 1 : 0 );
		
		sort( ALL( rates ), greater<int>() );
		if ( binary_search( rates.begin(), rates.begin() + R, elly, greater<int>() ) )
		{
			return 0;
		}
		
		return 1. / R;
	}
};