半分全列挙

半分全列挙について

タグ 半分全列挙

  • 探索範囲Nを半分に分割する
    • それぞれの探索範囲を探索する
    • 探索結果を合算してbinary search等で個数を求める

例; 典型

問題

解説

  • pythonの場合はbit全探索するよりitertoolsを使ったほうが早い(上限の個数を限定できるからか)
  • 分割した結果を合算するとき、L * Rを回すとTLEしてしまうので、二分探索をしてO(L log R)にする

解答

import itertools
import collections
import bisect

def main():
    N,K,P=map(int,input().split())
    *A,=map(int,input().split())

    LA, RA = A[:N//2], A[N//2:]

    L=collections.defaultdict(list)
    for k in range(K+1):
        for la in itertools.combinations(LA, k):
            sum_ = 0 if la == [] else sum(la)
            L[k].append(sum_)

    R=collections.defaultdict(list)
    for k in range(K+1):
        for ra in itertools.combinations(RA, k):
            sum_ = 0 if ra == [] else sum(ra)
            R[k].append(sum_)

    for key in list(L.keys()):
        L[key].sort()
    for key in list(R.keys()):
        R[key].sort()

    ans = 0
    for rk, rlst in R.items():
        rem = K-rk
        llst = L[rem]
        for r in rlst:
            ans += bisect.bisect_left(llst, P-r + 1)
    print(ans)

if __name__ == "__main__":
    main()