torus711 のアレ

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

TopCoder SRM 610, Division 2, Level 1 : DivideByZero

問題概要

 相異なる整数の集合が与えられる。この集合に対し、以下の処理を繰り返し適用する。

  • a > b なる二つの要素を選び、a を b で整数除算した値が集合に含まれなければ、これを集合に加える

それ以上操作を適用できなくなったときの、集合の要素数を求めよ。

解法

 集合に含まれる最大の値を N と表記します。
 集合に新たな要素を加えるとき、加えられる値は明らかに N より小さくなります。鳩ノ巣原理より、N より大きい回数の操作を適用することはできません。a, b の選び方を全て試したとしても操作一回あたり O( N^2 ) であり、全体では O( N^3 ) となるので、与えられた手順をそのまま実装することで解くことができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define FOR( v, c ) for ( auto &v : c )
#define ALL( c ) (c).begin(), (c).end()

class DivideByZero
{
public:
	int CountNumbers( vector <int> numbers )
	{
		vector<bool> cur( 101 ), next;
		FOR( n, numbers )
		{
			cur[n] = true;
		}

		do
		{
			next = cur;

			REP( a, 1, 101 )
			{
				REP( b, 1, a )
				{
					if ( cur[a] && cur[b] && !next[ a / b ] )
					{
						next[ a / b ] = true;
					}
				}
			}

			swap( cur, next );
		}
		while ( cur != next );

		return count( ALL( cur ), true );
	}
};