AtCoder Beginner Contest 184, F : Programming Contest

問題文

　https://atcoder.jp/contests/abc184/tasks/abc184_f

問題概要

　$N$ 項の正整数列 $\{ A_i \}$ が与えられる．$A$ の部分列であって総和が $T$ 以下となるものの内で，総和が最大のものの総和はいくらか？

制約

• $1 \leq N \leq 40$
• $! \leq T, A_i \leq 10^9$

解法

　$A$ からの要素の選び方 $2^N$ 通りをすべて試す事ができれば解けますが，それにはやや $N$ の制約が大きく，間に合いません．そこで，（やや天啓的ですが，）$A$ を前半と後半の半分に区切って別に処理することを考えます（界隈で「半分全列挙」と呼ばれるテクで，蟻本 [1] などに記載があります）．$2^{ \frac N 2 }$ 程度ならば全通り試せるので，それぞれのサマライズをうまくがっちゃんこできれば問題を解けます．
　半分に分けた内のどちらか適当な方について，要素の選び方を全通り試すとします．ある選び方について，そのときの総和が $s$ だったとすると，残りの半分の要素から $T - s$ を超えない範囲での最大値をとってくるのが，（先に固定した半分に対する）最適な選び方です．よって，残りの半分については，あり得る総和の内である値を超えない最大値を求められるようなデータのもち方をしておけばよいです．なので，std::set につっこんでおくか，ソート済みの std::vector に入れておいて二分探索をすることで欲しかったデータを高速にとってくることができます．
　計算量としては，$\Theta( 2^N )$ 個のデータをソートする部分に $O( 2^N \log 2^N )$ かかり，その後で $O( 2^N )$ 回の二分探索で $O( 2^N \log 2^N )$ がかかります．
　もう少し工夫するとソートが一回増える代わりに二分探索をしなくてよくなります．先に固定する部分から出てくる値が仮に昇順になっていれば，二分探索される値は必ず降順で出てくるので，先に固定する値が決まる度に二分探索をするのではなくて，一旦全部並べてからソートしてあげると，2 つのポインタをもって sweep するだけでよくなります．

参考文献

[1] 秋葉拓哉, 岩田陽一, & 北川宜稔. (2010). プログラミングコンテストチャレンジブック.

コード

constexpr auto INF = LIM< LL >::max() / 2;

int main()
{
	IN( int, N, T );
	VI A( N );
	cin >> A;

	const int n = N / 2;
	const int m = N - n;
	VT< LL > after_half( 1, -INF );
	REP( s, 1 << m )
	{
		LL r = 0;
		REP( i, m )
		{
			if ( s & 1 << i )
			{
				r += A[ n + i ];
			}
		}
		after_half.PB( r );
	}
	sort( ALL( after_half ) );

	VT< LL > befor_half;
	REP( s, 1 << n )
	{
		LL r = 0;
		REP( i, n )
		{
			if ( s & 1 << i )
			{
				r += A[i];
			}
		}
		befor_half.PB( r );
	}
	sort( ALL( befor_half ) );

	auto pos = end( after_half ) - 1;
	LL res = 0;
	FOR( r, befor_half )
	{
		for ( ; T - r < *pos; --pos );
		chmax( res, r + *pos );
	}
	cout << res << endl;

	return 0;
}