半分全列挙
参考
たのしい探索アルゴリズムの世界
例えば、数列
$ A_0 ,A_1,A_2,…A_n
についてm個選んで総和をkにできるか(重複あり)、という問題があったとき、
$ W
=
$ \frac{m}{2}
個の要素の選び方
$ n^\frac{m}{2}
通りそれぞれの総和
という数列を考える
これにより、Wを決めるだけで総和をkにするために必要な値が分かり、二分探索によって答えを求めることが出来る
#競プロ
#アルゴリズム
#探索