概要

\(N\) 棟の建物をすべて解体するときの費用の合計を最小化する解体順序を見つける問題です。

考察

この問題では、建物を解体する「順番」を最適化する必要があります。制約を見ると \(N \leq 19\) と非常に小さいため、すべての解体順序を考慮できる「ビットDP（bit DP）」が使えると推測できます。

建物 \(i\) を解体するときにかかる費用は、「建物 \(i\) の初期コスト \(C_i\)」に「すでに解体された建物から建物 \(i\) への影響 \(W\) の合計」を足したものになります。つまり、ある建物を解体する時点で「すでにどの建物が解体されているか」という状態が分かれば、その建物を解体するためのコストは一意に定まります。

したがって、「すでに解体された建物の集合 \(S\)」を状態として持つDPを考えます。 素朴にすべての順列 \(N!\) を試すと \(19! \approx 1.2 \times 10^{17}\) 通りとなりTLEになりますが、ビットDPを用いると状態の遷移をうまくまとめることができ、計算量を大幅に削減できます。

アルゴリズム

以下のビットDPを用います。

• 状態: dp[S] = 解体済みの建物の集合が \(S\)（ビットで表現）であるときの、費用合計の最小値。
• 初期状態: dp[0] = 0（何も解体していない状態、費用0）
• 遷移: 現在の状態 \(S\) から、まだ解体されていない建物 \(i\) を解体することを考えます。 次の状態は nextS = S | (1 << i) です。 このときかかる追加コストは、初期コスト \(C_i\) と「状態 \(S\) に含まれる各建物 \(k\) から \(i\) への影響 \(W_{k,i}\) の合計」です。 これを cost とすると、dp[nextS] = min(dp[nextS], dp[S] + cost) と遷移します。

影響の合計を求めるために、事前計算を行います。sum_W[S * N + i] を「集合 \(S\) に含まれる建物が解体されたことによって建物 \(i\) に加算された \(W\) の合計」とします。これを状態 \(S\) のループの中で、最下位の立っているビット（解体された建物）を取り出し、前の状態からの和として効率的に計算します。

最終的にすべての建物を解体し終えた状態 \((1 << N) - 1\) での dp の値が答えとなります。

計算量

• 時間計算量: \(O(2^N \cdot N)\)
• 空間計算量: \(O(2^N \cdot N)\)

実装のポイント

• \(N=19\) のとき、状態数 \(2^{19}\) と遷移 \(19\) の積は約 \(10^7\) となり、制限時間内に十分間に合います。

• 追加コストの計算時に、コストの合計値が int の範囲を超える可能性があるため、DP配列やコスト計算には long long を使用しています。

• sum_W の前計算では、__builtin_ctz(S) を用いて集合 \(S\) の中で最も番号が小さい（最下位のビットが立っている）要素を取り出すことで、遷移元の状態 \(S \setminus \{k\}\) から高速に値を引き継ぐことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<long long> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    vector<vector<int>> W(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> W[i][j];
        }
    }

    int M = 1 << N;
    vector<long long> dp(M, 1e18);
    vector<int> sum_W(M * N, 0);
    
    for (int S = 1; S < M; S++) {
        int k = __builtin_ctz(S);
        int prev = S ^ (1 << k);
        for (int i = 0; i < N; i++) {
            sum_W[S * N + i] = sum_W[prev * N + i] + W[k][i];
        }
    }

    dp[0] = 0;
    for (int S = 0; S < M; S++) {
        for (int i = 0; i < N; i++) {
            if (!(S & (1 << i))) {
                long long cost = C[i] + sum_W[S * N + i];
                int nextS = S | (1 << i);
                if (dp[nextS] > dp[S] + cost) {
                    dp[nextS] = dp[S] + cost;
                }
            }
        }
    }

    cout << dp[M - 1] << "\n";
    return 0;
}

この解説は or-glm5.2-high によって生成されました。