WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM622 Div1 Medium "Ethernet"

問題

TopCoder Statistics - Problem Statement

あなたは0からN-1までの番号が付けられたN個のコンピュータを持っている。これらは1つのネットワークとして繋がっている。ネットワークの構造はツリー状になっている。あなたはその状態の説明としてint配列のparentとdistが与えられる。これらint配列は、ちょうどN-1個の要素を持つ。iを0からN-2としたとき、i+1番目のコンピュータはparent[i]番目のコンピュータとケーブルで繋がれており、その長さはdist[i]である。

あなたはまた次のような意味を持つint maxDistが与えられる。

同じネットワーク上にある、任意の2つのコンピュータの距離はmaxDistを超えてはならない。
(2つのコンピュータの距離はそれらを繋ぐケーブルの長さの合計とする)

もし、現在のネットワークが上記の性質を満たしていなければ、あなたはそれをより小さないくつかのネットワークに分割しなくてはならない。

形式的に言えば、あなたはまず小さなネットワークの数Kを決め、それからK個のネットワークの1つにそれぞれのコンピュータを配置する必要がある。それは下記のような性質を満たさなければならない。

  • K個の新しいネットワークは元のツリーのサブツリーである。
  • 新しいネットワークの直径は、大きくてもmaxDistでなければならない。

上記のような性質を満たすように、元のネットワークをK個の新しいネットワークに分割したときの、最小のKを返せ。

制約

1 <= コンピュータの数 <= 50
1 <= ケーブルの長さ <= 500
1 <= maxDist <= 500



解法

TopCoder SRM 622 Div1 Medium Ethernet - simezi_tanの日記
コチラを参考にしました。m(_ _)m

dfsで木DPする。
dp[v][d] = 頂点vを根とするサブツリーで、使える長さがdとしたときの、ケーブルを切る最小の数

サブツリーには使えるケーブルの長さに以下のような2つの制限がある。

①・・・頂点から末端までの長さ
②・・・サブツリー内の直径

①は簡単で、もしvの子供cのケーブルを切るのであれば、頂点cを根とするサブツリー上で使える長さはmaxDistまで回復するため、dfs(c, maxDist)としてやる。繋げたままとするのであれば、e(v, c)だけ使える長さが減るので、dfs(c, d - e(v, c))としてやればよい。

問題は②で、サブツリー上においても、直径はmaxDist以下としなくてはならない。サブツリー内の直径は、子供の末端までの距離上位2つの合計であるため、一番長い距離を使う子供と、その距離を決め打ちしてやる。そうすると他の子供の使える距離がでてくるので、①と②の小さいほうをdとしてdfsを呼べばよい。

ソースコード

int G[55][55];
int N, D;
int dp[55][550];

class Ethernet {
public:

    int connect(vector <int> parent, vector <int> dist, int maxDist) {
        N = parent.size();
        D = maxDist;

        // グラフ作成
        memset(G, -1, sizeof(G));
        for (int i = 0; i < N; i++) {
            int v = i + 1;
            int u = parent[i];
            int d = dist[i];
            G[v][u] = G[u][v] = d;
        }

        // メモ初期化
        memset(dp, -1, sizeof(dp));

        return dfs(-1, 0, maxDist) + 1;
    }

    int dfs(int p, int v, int d) {

        int& res = dp[v][d];

        if (res == -1) {
            res = 10000;
            // どの子を最長にしてやろうか??
            for (int lc = 0; lc <= N; lc++) {
                if (G[v][lc] == -1 || lc == p) continue;
                //この子にどのくらいリソース分け与えてやろうか?
                for (int r = (D + 1) / 2; r <= D; r++) {
                    int cand = 0;
                    // 子で回す
                    for (int c = 0; c <= N; c++) {
                        if (G[v][c] == -1 || c == p) continue;
                        // 切る
                        int add = dfs(v, c, D) + 1;
                        // 繋ぐ
                        int rem = min(d, D - r);
                        if (lc == c) rem = min(d, r);
                        if (G[v][c] <= rem) add = min(add, dfs(v, c, rem - G[v][c]));
                        
                        cand += add;
                    }
                    res = min(res, cand);
                }
            }
            if (res == 10000) res = 0;
        } 

        return res;
    }
};