torus711 のアレ

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

AtCoder Regular Contest #017, C : 無駄なものが嫌いな人

問題概要

 整数が N ( ≦ 32 ) 個与えられる。これらの数からいくつかを選んで和を計算したときに X となる取り出し方は何通りあるか求めよ。

解法

 2^{32} 回のループを回すと TLE してしまうので、取り出し方を全て試すことはできません。また、与えられる値もそこそこ大きいので、DP のキーにすることもできません。従って、別の方法を考える必要があります。
 ここで着目するのは、N ≦ 32 という制約です。2^{32} はダメですが、指数を半分にした 2^{16} ならループを回すことができます。そこで、与えられた数を半分ずつに分割して上手く処理できないか考えます。分割されたグループのそれぞれを A, B と呼ぶことにして、それぞれ次のように処理します。

  • A について、取り出し方を全て試し、和の値から、取り出し方の総数を(ある程度高速に)求められるようにしておく
  • B について、取り出し方を全て試し、そのときの和を t としたとき、和が X - t となる A からの取り出し方の総数を答えに加算する

 まず A に関する処理について、配列インデックス→値 とすると MLE するので、数えるときは map を使います。取り出し方は高々 2^{16} 通りで、和の値の総数もこれ以下になるので、十分メモリに乗ります。次に B について、B から和が t となるように取り出したととすると、A からは和が X - t となるように取り出せば、全体の和を X にできるので、妥当であると分かります。二つのグループからの取り出し方を全て試しているので、漏れはありません。また、どちらの処理も M = N / 2 とすると map の計算量を含めて O( 2^M \log 2^M ) = O( M2^M ) でできるので、処理時間も十分高速です。

コード

typedef vector<int> VI;

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

inline void input( VI &as )
{
	FOR( a, as )
	{
		cin >> a;
	}
	return;
}

int sum( const VI &as, const int s )
{
	int res = 0;
	REP( i, 0, as.size() )
	{
		if ( s & 1 << i )
		{
			res += as[i];
		}
	}
	return res;
}

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

	int n, x;
	cin >> n >> x;
	const int m = n / 2;
	n -= m;

	VI as( n ), bs( m );
	input( as );
	input( bs );

	map<int,int> w2c;
	REP( s, 0, 1 << n )
	{
		w2c[ sum( as, s ) ]++;
	}

	int res = 0;
	REP( s, 0, 1 << m )
	{
		res += w2c[ x - sum( bs, s ) ];
	}

	cout << res << endl;

	return 0;
}