C - Synthetic Kadomatsu

C - Synthetic Kadomatsu。
かなり複雑なDFSを使う問題。

まず、合成魔法のみに注目して、延長/短縮魔法は絶対値で取れる、というあたりの勘所を理解することが重要になりそう

def solve():

    N, A, B, C = map(int, input().split())
    llist = [int(input()) for i in range(N)]
    inf = 10**9

    def dfs(cursol, a, b, c):
        # すべての竹に対して合成魔法を試したら、不足分は延長 or 短縮魔法を使う
        if cursol == N:
            return abs(A-a)+abs(B-b)+abs(C-c)-30 if min(a, b, c) > 0 else inf

        return min(
            dfs(cursol+1, a, b, c),
            # 合成魔法を使っているので+10が必要
            dfs(cursol+1, a+llist[cursol], b, c)+10,
            dfs(cursol+1, a, b+llist[cursol], c)+10,
            dfs(cursol+1, a, b, c+llist[cursol])+10
        )

    print(dfs(0, 0, 0, 0))


if __name__ == "__main__":  
    solve()