ABC119-C 「Synthetic Kadomatsu」

atcoder.jp
全探索系の問題ですが、競プロ初心者はかなりとっつきにくい問題だと思います。
僕もこの問題の解法を見たときは衝撃を受けました（？）

「竹の長さを変える魔法」と「2本の竹を1本に合成する魔法」がありますね。
竹の長さを変えるだけであれば、作りたい3本の竹の長さA, B, Cに最も近いものを用いればよさそう、というのは直感的に分かります。
厄介なのは合成魔法ですね。2本の竹を合成することができると、上で述べたような貪欲的な解法は難しそうです。

さて、A, B, Cの長さから、N本の竹のうちどれを用いるかを決めることは難しそうです。なので、N本の竹から3本の竹を作っていくことを考えましょう。すると、N本の竹それぞれの使い道は　①竹Aに使う　②竹Bに使う　③竹Cに使う　④どれにも使わない　の4通りがありますね。制約を見ると3<=N<=8なので、全部で4^8通りです。間に合いそうですね。すべての竹の使い道が決まれば、あとはA, B, Cそれぞれの長さを微調整するだけです。↓はDFSで全探索をするコードです。

const ll INF=1e9+7;

ll n,a,b,c;

vector<ll> l;

ll dfs(ll N, ll A, ll B, ll C){
    ll rec=INF;
    if(N==n){
        if(min({A,B,C})==0) return INF;
        rec=abs(A-a)+abs(B-b)+abs(C-c);
    }
    if(N<n){
        rec=min(rec,dfs(N+1, A+l[N], B, C)+10);
        rec=min(rec,dfs(N+1, A, B+l[N], C)+10);
        rec=min(rec,dfs(N+1, A, B, C+l[N])+10);
        rec=min(rec,dfs(N+1, A, B, C));
    }
    return rec;
}
int main()
{
    
    cin >> n >> a >> b >> c;
    rep(i,n){
        ll x;
        cin >> x;
        l.push_back(x);
    }
    cout << dfs(0LL,0LL,0LL,0LL)-30 << endl;
    return 0;
} 

消費MPを返すDFSのコードを確認します。

ll dfs(ll N, ll A, ll B, ll C)

まずは関数の引数です。Nは使い道を決めた竹の本数です。
N=A=B=C=0から始めます。

if(N==n){
        if(min({A,B,C})==0) return INF;
        rec=abs(A-a)+abs(B-b)+abs(C-c);
}

N=nですべての竹の使い道が決まった後は、竹の長さをA, B, Cに調整です。調整した長さの分だけMPが消費されますね。
ここで注意なのは、無から竹を生成できない、という点です。N本の竹をすべてA, Bに使ってしまったら、Cは作れませんよね。その場合はINFを返しておきましょう。

if(N<n){
        rec=min(rec,dfs(N+1, A+l[N], B, C)+10);
        rec=min(rec,dfs(N+1, A, B+l[N], C)+10);
        rec=min(rec,dfs(N+1, A, B, C+l[N])+10);
        rec=min(rec,dfs(N+1, A, B, C));
}

それまでは、N本目の竹をA, B, Cのどれに使うか（もしくはどれにも使わないか）を決めればよいです。

cout << dfs(0LL,0LL,0LL,0LL)-30 << endl;

A, B, Cに用いる竹のうち、最初の1本は合成していませんから、答えを出力するときは合成3回分の30を引いておきます。

実装自体はそこまで難しくありませんが、初心者にはなかなか浮かびにくい解法ですよね。
「直感に頼ると間違えて、アルゴリズムの力を使うと解くことができる問題」は競プロの問題として意味があると思いますし、アルゴリズムを勉強することの意義も少し見えてきそうな気がします。僕自身、全探索よりも先に貪欲的な考えをしがちです。直感に頼りすぎず、初歩的なアルゴリズムを適用する精度を磨くというのが今後の課題です。

同様の考え方をする問題で、yukicoder No.967 引き算をして門松列（その2、その3）という問題があります。是非解いてみてください。
yukicoder.me
yukicoder.me