SRM 492 div1 med: TimeTravellingTour

問題

解法

区間 dp っぽく解くことが出来ます。

まず前処理で, 各頂点間の最短距離を覚えておきましょう。この時, 頂点 0 と cities のどこかの頂点の距離が INF (要するに辿りつけない) だったらその頂点を調べるのは不可能なので -1 を返します。

他の場合は, dp[now][from][to] = (今頂点 now にいて, cities の from から to の頂点を調べたい時の, 最小コスト) とします。

すると, 最小コストは,
now -> v と普通に移動して, v で一定の区間 [from, m) を調べた後, now に(TimeTravel で)戻ってきて, その後の区間 [m, to) を調べる
という (v, m) の組み合わせの最小値で求めることが出来ます。過去に戻る起点として, now を使うイメージですね。

状態数が O(n^3) で, 各状態を求めるのに必要な計算が O(n^2) なので O(n^5) ですが AC することが出来ました。

オーダーを改善するために, dfs を, v を決める側と m を決める側に分けることも出来ます。これは O(n^4) です。

まとめ

見た目からは区間 dp を全く想像出来ない…と思ってたけど, よく考えると順列っぽかったら区間 dp を考えるというのはよくある話だった。反省。

O(n^5)

const ll INF = 1ll<<55;
const int MAXN = 55;
ll d[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXN];
int n, m;
vector<int> city;

// [from, to)
ll dfs(int now, int from, int to) {
    ll& ret = dp[now][from][to];
    if (ret >= 0) return ret;
    if (from >= to) return ret = 0;
    if (now == city[from]) return ret = dfs(now, from+1, to);
    ret = INF;
    for (int i = 0; i < n; i++) {
        for (int j = from; j < to; j++) {
            ret = min(ret, d[now][i] + dfs(i, from, j+1) + dfs(now, j+1, to));
        }
    }
    return ret;
}

class TimeTravellingTour {
public:
    long long determineCost(int N, vector <int> cities, vector <string> roads) {
        n = N;
        m = cities.size();
        city = cities;
        string ss;
        for (string s : roads) ss += s;
        for (char& c : ss) if (c == ',') c = ' ';
        istringstream is(ss);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = INF;
        {
            int x, y, w;
            while (is >> x >> y >> w) d[x][y] = d[y][x] = w;
        }
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        for (int el : cities) {
            if (d[0][el] >= INF) return -1;
        }
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0, m);
    }
};

O(n^4)

const ll INF = 1ll<<55;
const int MAXN = 55;
ll d[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXN];
ll dp2[MAXN][MAXN][MAXN];
int n, m;
vector<int> city;

ll dfs(int, int, int);

ll dfs2(int now, int from, int to) {
    ll& ret = dp2[now][from][to];
    if (ret >= 0) return ret;
    ret = INF;
    for (int i = from; i < to; i++) {
        ret = min(ret, dfs(now, from, i+1) + dfs(now, i+1, to));
    }
    return ret;
}

// [from, to)
ll dfs(int now, int from, int to) {
    ll& ret = dp[now][from][to];
    if (ret >= 0) return ret;
    if (from >= to) return ret = 0;
    if (now == city[from]) return ret = dfs(now, from+1, to);
    ret = INF;
    for (int i = 0; i < n; i++) {
        ret = min(ret, d[now][i] + dfs2(i, from, to));
    }
    return ret;
}

class TimeTravellingTour {
public:
    long long determineCost(int N, vector <int> cities, vector <string> roads) {
        n = N;
        m = cities.size();
        city = cities;
        string ss;
        for (string s : roads) ss += s;
        for (char& c : ss) if (c == ',') c = ' ';
        istringstream is(ss);
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = INF;
        {
            int x, y, w;
            while (is >> x >> y >> w) d[x][y] = d[y][x] = w;
        }
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        for (int el : cities) {
            if (d[0][el] >= INF) return -1;
        }
        memset(dp, -1, sizeof(dp));
        memset(dp2, -1, sizeof(dp2));
        return dfs(0, 0, m);
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 492 div1 med: TimeTravellingTour

問題

解法

まとめ