読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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

解法

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

全探索

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

動的計画法

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

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

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

  • dp[ i + 1 ][ j + S_i ] を 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:蟻本参照