Atcoder水色精進記録
ABC119
C - Synthetic Kadomatsu
https://atcoder.jp/contests/abc119/tasks/abc119_c
アルゴリズム・データ構造
全探索(DFS)
考察
延長、短縮、合成*竹の選択=3*8=24なので、選択肢が多い。順番固定で絞ることをできないかを検討
延長、短縮の後に合成と合成した後に延長、短縮はどちらもコスト、結果が同じである。
先に合成をした場合に計算が楽になりそう。
合成する竹はどうやって選ぶか?
→最終的な行き先が3本の竹のどれかor使わないかの4択
→全探索は4**Nのため可能
各竹がA,B,C,未使用のどこに割り振られるかが分かれば、
割り振られた竹の本数-1回合成＋(割り振られた竹の長さの合計-目的の長さ)の絶対値
で簡単に計算が可能
提出
感想
現在なら緑色中間くらい?