torus711 のアレ

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

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

問題概要

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

解法

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

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

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

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

とすると、求める期待値は E[ \sum_t f( t ) ] です。これは期待値の線形性から \sum_t E[ f( t ) ] と変形され、各ターン毎に勝つ確率の和を求めればよいことが分かります。
 Sothe のもつ、出すターンが未確定のカードの枚数を r とすれば、カードは等確率 \frac{ 1 }{ r } で選択されます。着目しているターンで Snuke が出すカードを a 、Sothe の持つターンが未確定のカードの集合を B とすれば、着目ターンで Snuke が勝つ確率は、\sum_{ b \in B }\frac{ 1 }{ r } \times ( a > b ) です(ただし、不等号は真のとき 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;
	}
}