[AtCoder] ABC 184 F – Programming Contest

2020年11月25日

問題

方針

半分全列挙

\( n = \min(20, N) \) として、問題を \( n \) と \( N – n \) 個に分けて考えます。前半の問題の集合を \( A \) とし、後半を \( B \) とします。\( A \) の \( n \) 個の問題から選んで \( T \) 分以下となる時間の総和は、\( 2^n \) 通りあることが分かります。これは、ビット全探索を用いて列挙できます。

\( A \)、\( B \) のそれぞれの時間の総和を昇順に並び替え、\( A \) からある時間 \( x \) を選んだとき、\( B \) の時間の総和 \( y \) として、\( x + y \leq T \) を満たす最大の \( y \) を探索します。これは、二分探索で実現できます。

分枝限定法

この問題はいわゆる 0-1 ナップサック問題において、価値と重さが等しいものであると解釈できるのできます。したがって、分枝限定法によって解くことができます。

コード

半分全列挙

分枝限定法