AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の51問目である「Typical Shop（★5）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【051 – Typical Shop（★5）】
考察
考えた内容の概要
この問題は、半分全列挙というアルゴリズムを用いて解くことができます。半分全列挙とは、全ての組み合わせを列挙する代わりに、データを二つに分けてそれぞれの組み合わせを列挙し、その結果を組み合わせるという方法です。
考えたことの内容
品物の数がN個であるため、全ての組み合わせを列挙すると2^N通りとなり、Nが大きい場合にはTLEになります。
そこで、半分全列挙を用いると、計算量を大幅に削減することができます。
実装した内容
具体的には、
- 品物を二つのグループに分け、それぞれのグループで全ての組み合わせを列挙し
- その後、それぞれの組み合わせの値段の合計がP円以下となる組み合わせを探し、その数をカウントします。
典型解法：半分全列挙
コード
from itertools import combinations
from bisect import bisect_right
# 入力
N, K, P = map(int, input().split())
A = list(map(int, input().split()))
# N=1の場合
if N == 1:
if A[0] <= P:
print(1)
else:
print(0)
exit()
# K=Nの場合
if K == N:
if sum(A)<= P:
print(1)
else:
print(0)
exit()
# 品物を二つのグループに分ける
head_half = N // 2
tail_half = N -head_half
first_half = A[:head_half]
second_half = A[head_half:]
# 各グループの全ての組み合わせを列挙
first_half_comb = [[] for _ in range(head_half+1)]
second_half_comb = [[] for _ in range(tail_half+1)]
for i in range(head_half+1):
for comb in combinations(first_half, i):
first_half_comb[i].append(sum(comb))
for i in range(tail_half+1):
for comb in combinations(second_half, i):
second_half_comb[i].append(sum(comb))
# ソート
for i in range(head_half+1):
first_half_comb[i].sort()
for i in range(tail_half+1):
second_half_comb[i].sort()
# 値段の合計がP円以下となる組み合わせを探す
ans =0
for i in range(max(0, K-tail_half), min(K+1, head_half+1)):
for p1 in first_half_comb[i]:
ind = bisect_right(second_half_comb[K-i], P - p1) # P-p1 以下の要素数
ans += ind
print(ans)
コメント