TopCoder, SRM 637, Division 1, Level 1 : GreaterGame

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13504&rd=16080

問題概要

　 枚のカードを使った 2 人ゲームをする。各カードには の範囲の整数値が書かれている。
　ゲーム開始前、プレイヤーはそれぞれ 枚ずつのカードを配られ、ゲームに使う順番を決める。
　ゲームは ターンからなり、各ターンにプレイヤーは事前に決めた順番通りカードを一枚ずつ開示する。書かれている値が大きいカードを出したプレイヤーは 1 点を得る。
　片方のプレイヤー Snuke について、配られたカードに書かれている数値を含む配列 が与えられる。他方のプレイヤー Sothe について、カードの出す順番の予測を表す配列 が与えられる。有効な について、 は ターン目に Sothe が出すカードである。 のとき、 ターン目に Sothe が出すカードが何かは分かっていない（提出ターンが不明なカードの内からランダムに 1 枚選択される）。
　Snuke が最適な戦略でプレイしたとき、Snuke が得ることのできる得点の期待値を求めよ。

解法

　Sothe の手が既知なターンでは、（可能であれば）確実に得点できるため、まずは手が分かっているターンについて最適な戦略を考えます。手が不明なターンで運ゲーをするとき、強いカードを持っている方が有利だと考えると、この時点では、点を得ることと同時に、強いカードを残すことも考えなければなりません。すなわち、次のような戦略が最適だろうと検討が付きます。

• 勝てるターンに於いては、勝てるカードの内最弱のものを出す
• どうやっても勝てないターンでは、持っているカードの内最弱のものを出す

　残りの運ゲー部分については、カードを出す順番を表す順列がランダムに 1 つ選択されると考えます。この場合、片方の順列を固定しても答えは変わらないので、Snuke 側の順列は固定して考えます。関数 を

• ターン目に Snuke が出すカードに対して、Sothe が負けるなら 1 、それ以外 0

とすると、求める期待値は です。これは期待値の線形性から と変形され、各ターン毎に勝つ確率の和を求めればよいことが分かります。
　Sothe のもつ、出すターンが未確定のカードの枚数を とすれば、カードは等確率 で選択されます。着目しているターンで Snuke が出すカードを 、Sothe の持つターンが未確定のカードの集合を とすれば、着目ターンで Snuke が勝つ確率は、 です（ただし、不等号は真のとき 1 、偽のとき 0 の値をもつとする）。（得点の値が 0 か 1 なので）この確率を未確定のターンに Snuke が出す全てのカードについて合計したものを、前半で求めた値に足せば答えが求まります。

コード

using VI = vector<int>; using VVI = vector<VI>;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

#define PB( n ) push_back( n )

class GreaterGame
{
public:
	double calc( vector <int> hand, vector <int> sothe )
	{
		const int N = hand.size();
		sort( ALL( hand ) );

		double res = 0;
		VT< bool > used( 2 * N );

		REP( i, 0, N )
		{
			if ( sothe[i] == -1 )
			{
				continue;
			}

			int idx = upper_bound( ALL( hand ), sothe[i] ) - hand.begin();
			for ( idx = idx == N ? 0 : idx; used[ hand[ idx ] - 1 ]; idx = idx + 1 == N ? 0 : idx + 1 );

			res += sothe[i] < hand[ idx ];
			used[ hand[ idx ] - 1 ] = true;
			used[ sothe[i] - 1 ] = true;
		}

		VVI hands( 2 );
		FOR( h, hand )
		{
			if ( !used[ h - 1 ] )
			{
				hands[0].PB( h );
				used[ h - 1 ] = true;
			}
		}
		REP( i, 0, 2 * N )
		{
			if ( !used[i] )
			{
				hands[1].PB( i + 1 );
			}
		}

		const double p = 1. / hands[1].size();
		FOR( a, hands[0] )
		{
			FOR( b, hands[1] )
			{
				res += ( b < a ) * p;
			}
		}

		return res;
	}
}