【深さ優先探索】ABC119 C - Synthetic KadomatsuをPythonで解いてみた

atcoder.jp

今日は難問です。

正直、手も足も出ませんでした。
そのため、今日は思考の過程というより、自分メモって感じです。

Atcoder probremだと水色レベル。
水色になりたいと思っている自分にとっては、辛いですね。
徐々に頑張っていきます。

解答の流れ

この問題のキーポイントは、竹の扱い方を限ることです。
その4つとは、
・長さAの竹の“材料”とする
・長さBの竹の“材料”とする
・長さCの竹の“材料”とする
・使わない
です。

この条件の下での竹の使い方は、その場合の長さの竹の材料を全て合成して竹を得たあと、延長魔法と縮小魔法のうち適切な方を適切な回数使い、コストを計算することです。

これを全ての竹に対して行い、得られた最小値が答えとなります。

コード実装

N, A, B, C = map(int, input().split())
L = [0]*N
for i in range(N):
    L[i] = int(input())
INF = 10 ** 9


def dfs(times, a, b, c):  #  a,b,c:現在の竹の長さ
    if times == N:
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # 適切な竹に対して、(A or B or Cに合成する) or (使わない)の場合に分ける
    no_pattern = dfs(times + 1, a, b, c)
    a_pattern = dfs(times + 1, a + L[times], b, c) + 10
    b_pattern = dfs(times + 1, a, b + L[times], c) + 10
    c_pattern = dfs(times + 1, a, b, c + L[times]) + 10

    return min(no_pattern, a_pattern, b_pattern, c_pattern)


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