きままにものづくり

日々の気付いたことなんかを書いてます。

POJ 3977 : Subset

問題

要素数N(N \leq 35)の数列が与えられる。その数列の中で空でない、総和がの絶対値が最小の部分列を求めよ。

解法

半分全列挙と二分探索。以下、注意点

  • 2つに分割した集合のどちらか片方のみに答えの数値が含まれている場合を考慮する。つまり、集合1と集合2の組み合わせの探索だけでなく、集合1と2それぞれ単独で探索する必要がある。ただし、for文を回す方の集合に空の要素を入れておけば、それぞれ単独で探索する必要はない。
  • lower_boundにより見つけた値は、目標値以上の値になっているので目標値未満で目標値との差分の絶対値が小さい値を探索する必要がある。uniqueをしていればその値は、lower_boundにより1つ手前の値になる。

計算量

KlogK
K : 2つに分割した際の要素数 K=2^{\frac{N}{2}}

コード