今日は難問です。
正直、手も足も出ませんでした。
そのため、今日は思考の過程というより、自分メモって感じです。
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))
解答を見たので、もちろんACでした。
水色コーダーへの道は遠い。