Python3: お菓子の詰め合わせ (paizaランク A 相当)やってみた

おもしろそうなのでやってみました。

from itertools import combinations

length_from = (
    lambda N: lambda amount: lambda sorteds:
        next(
            length
            for length in range(N, 0, -1)
            if sum(sorteds[:length]) <= amount
            )
    )

remain_from = (
    lambda length: lambda amount: lambda sorteds:
        min(
            diff
            for c in combinations(sorteds, length)
            if (diff := amount - sum(c)) >= 0
            )
    )

N, AMOUNT = map(int, input().split())
XS = [int(input()) for _ in range(N)]

sorteds = sorted(XS)
length = length_from(N)(AMOUNT)(sorteds)
remain = remain_from(length)(AMOUNT)(sorteds)

print(remain)

ソートして小さい方からの部分和を考えると、いくつ買えるかがわかります。あとはその個数の組み合わせで一番残金の少ないのを探せばよい。
ソートと部分的な組み合わせの合わせ技で、特に個数の多いときの計算量はだいぶ減ってると思います。