半分全列挙
atcoder.jp 解法 全探索しようとするとO(2N)になり、制約が N ≦ 40 なのでこれでは間に合わない。 そこで、半分全列挙というテクニック使ってO(2N/2)で解くことを考える。 N個の問題を2つのグループに分けて、それぞれのグループごとに問題の選び方を全探索…
atcoder.jp 制約を見て半分全列挙とかいうやつじゃないか、と気づいた。 勉強したことなかったので記事にします。 半分全列挙について 簡単にいうとbit全探索もしくは何重かfor文全探索を、二分探索などで高速化しようという考え方のこと。 下の記事の解説が…