【ABC180】E - Traveling Salesman among Aerial Cities

atcoder.jp

bitDPについて初めて学んだのでメモしておく。

bitDPとは？

下の記事たちがわかりやすい。

algo-logic.info

qiita.com

解法

巡回セールスマン問題であることが制約や問題名から読み取れる。
この問題の説明は下の記事でもされているので省く。
algo-logic.info

dp[S]ではなく、dp[S][v]としているのは、巡回セールスマン問題では、順番次第で移動コストが違うため。
上の記事では、実装についての詳しい解説がなかったので、下に詳しいコメントをつけた実装を載せておく。

実装

メモ化再帰で実装した。

long long N;
long long rec(int S, int v, vector<vint> &memo, vector<vint> &G) {
    if (S == 0) { // 出発地点を定める(一周して元の位置に戻ってくる必要があるため)
       if (v == 0) return 0; // 出発地点が固定された問題なのでv=0の時だけ0を返す
       else return INF64; // それ以外を出発点にするとおかしくなる
    }

    if (!(S & (1 << v))) return INF64; // 都市vに訪れたフラグが立っていない場合はreturn
    if (memo[S][v] != INF64) return memo[S][v]; // メモ化を活用

    REP (i, N) {
        // S & ~(1<<v)は都市vのフラグだけを0にしている
        // rec(S & ~(1<<v), i, memo, G):  都市vを除いた集合で最後に都市iを訪れた時の最小距離
        chmin(memo[S][v], rec(S & ~(1<<v), i, memo, G) + G[i][v]);
    }

    return memo[S][v];
}

void solve(long long N, std::vector<long long> X, std::vector<long long> Y, std::vector<long long> Z){
    vector<vector<ll>> memo((1 << N), vector<ll>(N, INF64));
    vector<vector<ll>> G(N, vector<ll>(N, INF64));
    REP (i, N) REP (j, N) G[i][j] = abs(X[i] - X[j]) + abs(Y[i] - Y[j]) + max(0LL, Z[j] - Z[i]);

    c(rec((1 << N)-1, 0, memo, G))
    
}

罠

最初、下のように実装していたがこの問題では、うまくいかない。

long long rec(int S, int v, vector<vint> &memo, vector<vint> &G) {
    if (S == 0) {
       if (v == 0) return 0;
       else return INF64;
    }

    if (memo[S][v] != INF64) return memo[S][v];

    REP (i, N) {
        if (S & (1 << i)) chmin(memo[S][v], rec(S & ~(1<<v), i, memo, G) + G[i][v]);
    }

    return memo[S][v];
}

集合Sに都市iが含まれるかどうかの判定をforループの中でしていたのだが、これだとS=0の時にうまくいかない。
というのも、S=1の時にS=0, v=0に遷移できない。

最初に載せた実装のようにS=0の判定より後に集合Sに都市vが含まれるかどうかを判定することで解決できる。