TopCoder, SRM 621, Division 2, Level 2 : NumbersChallenge

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13166&rd=15854

問題概要

　整数の（多重）集合 S が与えられる。S の部分和として現れない最小の非負整数を求めよ。
　

解法

　二通りの解法について書きます。一つは全探索、他方は動的計画法です。

全探索

　S の各要素について、使うか否かを決めていくことを考えます。この場合選び方の総数は となりますが、|S| の制約が小さいので計算可能な範囲に収まります。要素の選択を全通り試して部分和を列挙してから、それに含まれない最小の非負整数を探します。

動的計画法

　部分和問題は動的計画法の典型的な問題と言えます。以下のように状態をとります。

• dp[ i 個の要素について考慮したとき ][ 整数 j を ] := 作れるか否か

　dp[ i ][ j ] からの更新は、 を使うか否かを両方試すので、

• dp[ i + 1 ][ j + ] を dp[ i ][ j ] との論理和で更新
• dp[ i + 1 ][ j ] を dp[ i ][ j ] との論理和で更新

の二通りになります。
　計算が終わった後、dp[ |S| ][ j ] が false となる最小の j が答えです。
　以下の実装では、dp テーブルを一次元にするテクニック*1を使っています。

コード（全探索）

template < typename T = int > using LIM = numeric_limits<T>;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EXIST( c, e ) ( (c).find( e ) != (c).end() )

class NumbersChallenge
{
public:
	int MinNumber( vector <int> S )
	{
		int N = S.size();

		set<int> res;
		REP( s, 0, 1 << N )
		{
			int tmp = 0;
			REP( i, 0, N )
			{
				if ( s & 1 << i )
				{
					tmp += S[i];
				}
			}
			res.insert( tmp );
		}

		for ( int i = 1; ;i++ )
		{
			if ( !EXIST( res, i ) )
			{
				return i;
			}
		}
		return -1;
	}
};

コード（動的計画法）

using VI = vector<int>;

#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) (c).begin(), (c).end()

constexpr int MAX = 20 * 100000;

class NumbersChallenge
{
public:
	int MinNumber( vector <int> S )
	{
		VI dp( MAX + 100001 );
		dp[0] = 1;

		FOR( a, S )
		{
			for ( int i = MAX; 0 <= i; i-- )
			{
				dp[ i + a ] |= dp[i];
			}
		}

		return find( ALL( dp ), false ) - dp.begin();
	}
};

*1:蟻本参照