概要
次のような手順で進められる二人ゲームがある。
- 両プレイヤーに、'0' と '1' からなる長さ 2n の文字列が与えられる
- 次の操作が可能である間、両プレイヤーは次の操作を交互にする
- まだ選ばたことのない整数 k を一つ選ぶ
- 自分の持つ文字列を s として、 の文字を自分の紙に書き下す
- 両プレイヤーは、自分の紙に書いてある文字を好きに並び替えて数を作る。
- 並び替えてできた数が大きい方のプレイヤーが勝つ。等しければ引き分け。
両プレイヤーが最善を尽くした場合の結果(先攻の勝利|後攻の勝利|引き分け)を判定せよ。
解法
2n の制約から、両者の持つ数字の桁数は等しくなります。
更に、自由に並び替えることができるので、全ての 1 を左に寄せることで、最大の値を構成できます。
両者の作りうる最大の値を比較する場合、1 の数が多い方が大きい数ということになります。
1 の数を最大化しようとする場合、k を選ぶ際の優先順位は次のようになります。
- 両方 1 となるような k
- 自分だけ 1 となるような k
- 自分は 0 だが相手は 1 となるような k
- 残り(両方 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; }