ABC119 C - Synthetic Kadomatsu
解法
全探索をすればよいです。
Aに使う竹、Bに使う竹、Cに使う竹の3種類にまず分けます。
これは、bitで竹を表現して全探索するとやりやすいかと思います。
ビットの部分集合を列挙する方法はこちらをご覧ください。
さて、その後は、それぞれについてコストを計算します。Aについて計算してみます。
まず、のコストが必要です。
あとは、
を計算して、これらを足し合わせると、Aを作成するのにかかるコストが計算できます。
同様にB,Cについても行えば、その合計値の最小値を探すことで、答えを求めることができます。
感想
bitの部分集合を列挙する方法を探すのに数分かかりました(他の方とのトーク履歴に残っているので、いつもそこから探しています…ｗ)。そして、誤読をしていて、全ての竹を使わないと勘違いしていたり、そもそもバグを埋め込みすぎていたりしたため、先にDに飛びました。
なかなか実装の重いCではないかなと思います…
