This page looks best with JavaScript enabled

AtCoder Beginner Contest 119 C – Synthetic Kadomatsu 感想

 ·  ☕ 2 min read  ·  ✍️ reud · 👀... views

ABC119C お疲れ様でした 僕はCが解けずに爆死しました。

ちゃんと解説を読んで理解をする必要があるため、ソースにひたすらコメントを打ってました。

理解しない限り同じ問題が解けないからねしょうがないね。

特に再帰処理での全探索が全く書けなかったため、非常に今回は辛かった・・・()

そしてこのような感じで理解しましたとさ。

<br /># 入力
N, A, B, C = map(int, input().split())
L = [int(input()) for i in range(N)]

INF = 10 ** 9


def dfs(cursor, a, b, c):  # cursor:カーソル a,b,c:現在の竹の長さ
    if cursor == N:  # cursorが最後まで行ったら終了する。
        return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF
    # abs(a - A) + abs(b - B) + abs(c - C) - 30 でなぜ30を減じているのかというと、
    # dfs(0,0,0)
    # dfs(0,0,0,0)で始まる以上、最初に選ばれるa,b,cを決定する際にもコストが10増加してしまうからである。
    # また、全探索を行う中で、a,b,cの初期値が0,0,0である以上、a,b,cのどれかが0のまま終了する場合が存在する。
    # この場合はa,b,cに竹が対応してないと言えるため、解にはならない、そこで三項演算子を利用して
    # その場合についてコストをINFとしている

    # 以下は4**Nで展開される再起処理となる。
    # カーソルの当たっている竹に対して、(A or B or Cに合成する) or (合成しない)の場合に分ける
    no_compound_pattern = dfs(cursor+1, a, b, c)
    compound_a_pattern = dfs(cursor+1, a + L[cursor], b, c)+10
    compound_b_pattern = dfs(cursor+1, a, b + L[cursor], c)+10
    compound_c_pattern = dfs(cursor+1, a, b, c + L[cursor])+10

    # 結果的に以下の値が返るのはそれぞれのパターンのコストが決定されてからなので
    # 以下のコードは最終的なコストの最小値
    return min(no_compound_pattern, compound_a_pattern, compound_b_pattern, compound_c_pattern)


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

個人的に一番大事だと思うところは、a,b,cのベースとa,b,c,に合成する素材で分けて考えていたのですが、

そもそもa,b,cのベースを0としてしまえば、a,b,cのベースとなる竹を選択するコードとa,b,c,に合成する素材を選択するコードで分ける必要がなくなり、a,b,cに合成する素材を選択するコード部分だけ書けば良いようになるという部分です。

ベースが0のままだった場合はコストをINFにするという処理を書けば簡単に共通化出来ました。

かなり久しぶりに再帰処理を使ったコードを書いた気がするので、出来るだけ定着させていきたいですね。・・・

Share on

reud
WRITTEN BY
reud
Stundent