[AtCoder] ABC 119 C – Synthetic Kadomatsu

問題

方針

制約から考える

竹の本数 \( N \) は最大で \( 8 \) 本であることに注目すると、合成魔法を基準に考えていけばよいことが思いつきます。ある竹 \( i \) について、合成魔法を適用できる竹は \( 3 \) 通りであり、適用しない通りを考えると、\( 4 \) 通りのパターンが考えられます。したがって、合成魔法について全探索を行うには、\( 4^N \) 通り調べることになります。

深さ優先探索による全探索

ある状態から枝分かれして新しい状態に遷移するような問題を解くには、深さ優先探索を使って解くことができます。樹形図や木をイメージすると分かりやすいのかもしれません。

コード

提出したコード

深さ優先探索

void dfs(int cost, int n, int a, int b, int c) {
  if (n == N) {
    if (a == 0 || b == 0 || c == 0) return;
    cost += abs(A - a) + abs(B - b) + abs(C - c) - 30;
    v = min(v, cost);
    return;
  }
  dfs(cost + 10, n + 1, a + l[n], b, c);
  dfs(cost + 10, n + 1, a , b + l[n], c);
  dfs(cost + 10, n + 1, a, b, c + l[n]);
  dfs(cost + 0, n + 1, a, b, c);
}

上記のコードにおいて、\( v \) は目的を達成する最小の MP とします。そして、長さを \( A, B, C \) にする竹の現在の長さを \( a, b, c \) とします。また、現在の深さを \( n \)、コストを \( cost \) とします。合成魔法を使う度にコストが \( 10 \) 増加しますが、深さが \( n = N \) となった時にコストを \( -30 \) と計算しています。これは、長さ \( 0 \) の竹に合成を行うときはコストが掛からないのを考慮しているためです。

また、\( n = N\) のとき、竹の長さが \( 0 \) となっているものがあるときは、延長魔法を使うことができないので、このときのコストは正しくありません。最後に、延長や伸縮魔法を使って長さを揃えます。

AtCoder,探索,深さ優先探索全探索

Posted by ヤマカサ