torus711 のアレ

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

Codeforces #235, C : Team

問題概要

 n 個の '0' と m 個の '1' を、以下の二つの condition を共に満たすような並べ方で並べよ。そのような並べ方が存在しないとき、-1 で示せ。

  • '0' 同士は隣接しない
  • 連続する 3 個の文字が '1' となることは無い

解法

 まず、一つ目の条件から、二つの '0' の間に 1 個以上の '1' を挟む必要があります。また、'1' の配置は、'0' の間に 1 〜 2 個ずつ配置するか、一番外側に 1 〜 2 個くっつけるかしかできません。これらの制約から、並べ方が存在しないケースは次のいずれかの条件を満たすときです。

  • m < n - 1 を満たす
  • ( n - 1 ) * 2 + 4 < m を満たす

いずれの条件も満たさないとき、適切に並べることで目標を達成することができます。
 並べる際には、"010101010" のような列に対し、余った '1' を挿入可能な位置に挿入すると考えると分かりやすいと思います。配置の戦略としては、

  1. '0' に挟むだけでは並べきれない '1' があれば、先頭に( 2 個までの範囲で)置く
  2. (置くべき '0' があれば)1 個置く
  3. '0' が残っている間、次のように繰り返す
    1. 残りの '0' より '1' の方が多いならば 2 個、そうでないなら 1 個の '1' を置く
    2. 1 個の '0' を置く
  4. 最後に、'1' が余っているならばそれを末尾に付ける

コード

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

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

	int n0, n1;
	cin >> n0 >> n1;

	if ( n1 < n0 - 1 || ( n0 - 1 ) * 2 + 4 < n1 )
	{
		cout << -1 << endl;
		return 0;
	}

	for ( int iteration = 0; iteration < 2 && ( n0 - 1 ) * 2 + 2 < n1; iteration++ )
	{
		cout << 1;
		n1--;
	}
	if ( 0 < n0 )
	{
		cout << 0;
		n0--;
	}

	while ( 0 < n0 )
	{
		if ( n0 < n1 )
		{
			cout << 1;
			n1--;
		}
		cout << 10;
		n1--;
		n0--;
	}

	while ( 0 < n1 )
	{
		cout << 1;
		n1--;
	}
	cout << endl;

	return 0;
}