torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Croc Champ 2013, Round 2, Div2 Edition, C : Weird Game

概要

次のような手順で進められる二人ゲームがある。

  1. 両プレイヤーに、'0' と '1' からなる長さ 2n の文字列が与えられる
  2. 次の操作が可能である間、両プレイヤーは次の操作を交互にする
    1. まだ選ばたことのない整数 k を一つ選ぶ
    2. 自分の持つ文字列を s として、s_k の文字を自分の紙に書き下す
  3. 両プレイヤーは、自分の紙に書いてある文字を好きに並び替えて数を作る。
  4. 並び替えてできた数が大きい方のプレイヤーが勝つ。等しければ引き分け。

両プレイヤーが最善を尽くした場合の結果(先攻の勝利|後攻の勝利|引き分け)を判定せよ。

解法

2n の制約から、両者の持つ数字の桁数は等しくなります。
更に、自由に並び替えることができるので、全ての 1 を左に寄せることで、最大の値を構成できます。
両者の作りうる最大の値を比較する場合、1 の数が多い方が大きい数ということになります。

1 の数を最大化しようとする場合、k を選ぶ際の優先順位は次のようになります。

  1. 両方 1 となるような k
  2. 自分だけ 1 となるような k
  3. 自分は 0 だが相手は 1 となるような k
  4. 残り(両方 0 となるような k )

コード

typedef vector<string> VS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	string s, t;
	cin >> s >> t;

	int both = 0, a = 0, b = 0, none = 0;
	REP( i, 0, 2 * n )
	{
		if ( s[i] == '1' && t[i] == '1' )
		{
			both++;
		}
		else if ( s[i] == '1' )
		{
			a++;

		}
		else if ( t[i] == '1' )
		{
			b++;
		}
		else
		{
			none++;
		}
	}

	VS priority( both, "11" );
	{
		int f = both % 2;
		REP( i, 0, min( a, b ) * 2 )
		{
			priority.PB( f++ % 2 ? "01" : "10" );
		}
		REP( i, 0, max( a, b ) - min( a, b ) )
		{
			priority.PB( a < b ? "01" : "10" );
		}
		REP( i, 0, none )
		{
			priority.PB( "00" );
		}
	}
	
	int res1 = 0, res2 = 0;
	REP( i, 0, 2 * n )
	{
		( i % 2 ? res2 : res1 ) += priority[i][ i % 2 ] == '1';
	}

	if ( res1 == res2 )
	{
		cout << "Draw";
	}
	else if ( res1 > res2 )
	{
		cout << "First";
	}
	else
	{
		cout << "Second";
	}
	cout << endl;


	return 0;
}