Codeforces #231, C : Dominoes

問題文

http://codeforces.com/contest/394/problem/C

問題概要

　 のフィールドに文字列 = { "00","01, "10, "11" } が並んでいる。この文字列に対し、以下の二つの操作を任意回できる。

• 場所を並び替える
• 文字列を反転する

　列の総和の最大値を最小化するように動かした後の盤面を一つ出力せよ。

解法

　まず、二つの文字列の組み合わせ方について考えます。{ "01", "10" } か { "00", "11" } と縦に並べることで、二行埋めつつそのどちらの列も総和が 1 しか増えないようにできます。また、"01" と "10" は互いに変換可能なので、適当に変換しつつ一つずつ置いていくと高々 1 個だけ余ります。
　並べるときの順序ですが、総和が最大となる列の総和を最小化したいので、総和の最大値と最小値の差が小さくなるように配置していくことになります（大きく乖離する場合そこを入れ替えると最大値を小さくできる）。これは、総和が少ない列から（＝左上から横方向に）総和が増えるものを置いていくことで達成できます。また、二つずつの組み合わせを置き終わった後は、"00" と "11" はいずれか一方しか存在せず、"01" と "11" はいずれかが一つしか存在しません。従って、同様に左上から右方向に "01" または "10" 優先で配置していけば、総和の最大値を最小化できます。

コード

typedef vector<int> VI;
typedef vector<string> VS;

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

map<string,int> dominoType = {
	{ "00", 0 },
	{ "01", 1 },
	{ "10", 2 },
	{ "11", 3 }
};

string domino( const int n )
{
	string res( 2, '0' );
	REP( i, 0, 2 )
	{
		if ( n & 1 << i )
		{
			res[i] = '1';
		}
	}
	return res;
}

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

	int h, w;
	cin >> h >> w;

	VI counts( 4 );
	REP( i, 0, h * w )
	{
		string s;
		cin >> s;
		counts[ dominoType[s] ]++;
	}

	if ( counts[1] > counts[2] )
	{
		swap( counts[1], counts[2] );
	}

	{
		const int d = abs( counts[1] - counts[2] ) / 2;
		counts[1] += d;
		counts[2] -= d;
	}

	vector<VS> res( h, VS( w ) );
	for ( int i = 0; i + 1 < h; i += 2 )
	{
		REP( j, 0, w )
		{
			if ( res[i][j] == "" && 1 <= min( counts[1], counts[2] ) )
			{
				res[i][j] = "01";
				res[ i + 1 ][j] = "10";
				counts[1]--;
				counts[2]--;
			}
		}
	}

	for ( int i = 0; i + 1 < h; i += 2 )
	{
		REP( j, 0, w )
		{
			if ( res[i][j] == "" && 1 <= min( counts[0], counts[3] ) )
			{
				res[i][j] = "00";
				res[ i + 1 ][j] = "11";
				counts[0]--;
				counts[3]--;
			}
		}
	}

	REP( i, 0, h )
	{
		REP( j, 0, w )
		{
			if ( res[i][j] == "" )
			{
				REP( k, 0, 4 )
				{
					if ( 0 < counts[k] )
					{
						res[i][j] = domino( k );
						counts[k]--;
						break;
					}
				}
			}
		}
	}

	REP( i, 0, h )
	{
		REP( j, 0, w )
		{
			cout << ( j ? " " : "" ) << res[i][j];
		}
		cout << endl;
	}

	return 0;
}