問題
ポイント
競プロに親しみがある方だとこの問題を見たときに
ナップサック問題と似ている→動的計画法で解ける！と思われるかもしれません。
ただ、残念ながらこの問題を動的計画法で解くことはできないのです・・・。
理由は値段の合計Pと、各商品の値段Aiの上限が大きい（10の18乗）ことにあります。
動的計画法を行うにははじめに0~P、0~Aiまでの配列を用意しなければならないのですが、
リストのデータ型では10の18乗までのインデックスには対応していません。
・・・かと言って全部の商品の選び方を検証しようとすれば最高で2の40乗の計算を
しなければならず、TLEとなってしまいます。
ではどうするか。
ここでは半分全列挙という方法を利用します。※正式な呼称ではないかもしれません・・・。
次の手順で解法を求めていきます。
①商品を2つのグループに分ける：グループ1とグループ2とする
②グループ1と2それぞれで商品の組み合わせをすべて求める。
③グループ1からある組み合わせを選び、その値段の合計をc円とする
④グループ2からP-c円以下となる組み合わせを調べる
ポイントは①と②です。それぞれのグループの商品の選び方を調べるのには最高でも
2 x 2の20乗しかかかりません。そのためTLEを回避できます。
以上を踏まえ、実装したコードはこちらです。
※④でP-i円以下の組み合わせを調べる際、二分探索という方法を利用しています。
二分探索の詳細は下記記事が参考になります。
AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法
コード
def main():
import sys
import bisect
from itertools import combinations
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
N, K, P = map(int, input().split())
A = list(map(int, input().split()))
group1, group2 = A[:N//2], A[N//2:]
group1_price = [[] for _ in range(K + 1)] # 0~K個選んだときの価格を格納
for i in range(K+1):
for c in combinations(group1, i): # group1からi個選んだときの組み合わせ
group1_price[i].append(sum(c))
group1_price[i].sort() # 価格を昇順にソートする→後で二分探索を行うため
ans = 0
for i in range(K+1):
for c in combinations(group2, i): # group2からi個選んだときの組み合わせ
# group1からK-i個選んだときの組み合わせの内、金額がP-sum(c)以下の数
# 二分探索を行う
index = bisect.bisect(group1_price[K-i], (P - sum(c)))
ans += index
print(ans)
if __name__ == '__main__':
main()
