アルゴリズムの中で、ありうるものを全パターン列挙して、その中で探索するものがある。半分全列挙としては、全部列挙するには計算量が足りないけど、半分ずつ列挙するのならば、二分探索やしゃくとりで計算量を落として計算できる場合がある。くわしくは蟻本で。
蟻本にないと思われる奴を載せる
蟻本にないと思われる奴を載せる
前半と後半の二つに配列を分けて、それらを全列挙
二つの配列A,Bにそれぞれの全データの半分の全列挙を載せて、そこでやるパターンがある。説明しづらいので、例題を見よう。
AOJ1161 Verbal Arithmetic (AOJICPC400)
同類項の妙技の続き。A + 2B + 3C - 4D = 0のような数式の解を求めるとき、A~Bを前半、C~Dを後半として分けて、二つの全列挙列を作ることができる。あとは、あらかじめソートしておけば、二分探索でO(nlogn)で解くことができる。
また、これは尺取法でさらなる高速化が可能である
また、これは尺取法でさらなる高速化が可能である
