半分全列挙のはなし

最近Atcoderの青difficulty問題を解き切ったので、それに絡めて記事を書いていこうと思います。初回は半分全列挙についてです。半分全列挙はその名の通り半分だけ状態を列挙する方法です。これだけだと何のことかわからないと思うので、例題を用いて考えてみましょう。 例題 パッと問題文を見るとDPが思い浮かぶと思いますが、制約をよく見るとX<10⁹なので難しいです。一方、N<32と非常に小さいことに注目しましょう。ただし、荷物のあるなしの全ての状態を考えると2³²~10⁹となり、間に合いません。そこで、荷物を半分づつグループに分けてそれぞれグループ１、グループ２と呼ぶことにします。簡単のためN=2nするととそれぞれのグループについてそこから何個か選ぶ組み合わせは2ⁿなので全て列挙することができます。まずグループ１の状態を固定しその大きさをw1とします。すると問題の条件を満たすためには、グループ２から取ってきた荷物の重さの合計がw2 = W-w1となる必要があります。これを満たす選び方の数はグループ２の状態を全て列挙しているので簡単に求めることができます。

from bisect import *
N, X = map(int, input().split())
w = [int(input()) for _ in range(N)]
weight1 = []
for s in range(1<<(N//2)):
    res = 0
    for i in range(N//2):
        if s & 1<<i:
            res+=w[i]
    weight1.append(res)
weight2 = []
n = N-N//2
for s in range(1<<n):
    res = 0
    for i in range(n):
        if s & 1<<i:
            res+=w[N//2+i]
    weight2.append(res)
weight1.sort()
weight2.sort()
ans = 0
for w in weight1:
    l = bisect_left(weight2, X-w)
    r = bisect_right(weight2, X-w)
    ans+=(r-l)
print(ans)

N~36の時はだいたい半分全列挙だと思いましょう。 類題