ICPC国内予選2016 E問題 : 3Dプリント

問題. 3Dプリント

3次元空間に $n$ 個の同じ大きさで同じ向きの立方体の配置候補が与えられるので，その中からちょうど $k$ 個選び立方体を連結で表面積が最小となるように配置せよ．配置候補の各立方体は3個以上とは重ならず，3個以上の立方体が共有点を持つことはない．

制約： $1 \le k \le n \le 2,000$ ，　 $3 \le s$ (立方体の一辺の長さ) $\le 100$

解法. 幾何 + 全探索

配置候補に置かれた立方体を頂点として，重なる立方体の間に辺を張って構成される無向グラフ $G = (V, E)$ を考える．2つの立方体が重ならない場合の表面積は $6s^2$ となる．また，重なる場合は重なる部分が直方体となり，その表面積を $x$ とすると2つの立方体の表面積は $6s^2 - x$ となる．したがって， $G$ の各辺の重みを重なる部分の直方体の表面積とすると，考える問題は $G$ の重み最大で連結なサイズ $k$ の辺部分集合を選ぶ問題となる．問題の配置候補の制約から $G$ の各連結成分は道か閉路となり，候補となる辺部分集合は道か閉路となるので深さ優先探索で全探索する．
ここで，2つの立方体が重なるとして重なる部分の直方体の表面積を求めることを考える．2つの立方体の座標をそれぞれ $(x_1, y_1, z_1), (x_2, y_2, z_2)$ とする．このとき，重なる部分の直方体の各座標の辺の長さは $(d_1, d_2, d_3) = (s - |x_1 - x_2|, s - |y_1 - y_2|, s - |z_1 - z_2|)$ となるので，表面積は $2d_1d_2 + 2d_1d_3 + 2d_2 d_3$ となる．

計算時間： $O(n^2)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
struct Edge {
    int dst;
    ll w;
    Edge() {}
    Edge(ll d, ll w) : dst(d), w(w) {}
};
using Graph = vector<vector<Edge>>;
struct Cube { ll p[3]; };

// グラフを構成する
Graph MakeGraph(const int n, const int s, vector<Cube> &c) {
    Graph g(n);
    ll d[3];

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = 0; k < 3; ++k)
                d[k] = s - abs(c[i].p[k] - c[j].p[k]);

            // c[i]とc[j]は交差しない
            if (min({d[0], d[1], d[2]}) <= 0) continue;

            ll w = 2 * d[0] * d[1] + 2 * d[0] * d[2] + 2 * d[1] * d[2];
            g[i].emplace_back(Edge(j, w));
            g[j].emplace_back(Edge(i, w));
        }
    }

    return g;
}

ll Dfs(const int start, const int prev, const int cur, int size, const Graph &g) {
    if (size == 0) {
        if ((g[cur].size() == 2) && ((g[cur][0].dst == start && g[cur][0].dst != prev)
             || (g[cur][1].dst == start && g[cur][1].dst != prev)))
            return (g[cur][0].dst == start) ? g[cur][0].w : g[cur][1].w;
        else
            return 0;
    }

    ll max_w = -1;
    for (const auto &e : g[cur])
        if (e.dst != prev) {
            const ll res = Dfs(start, cur, e.dst, size - 1, g);
            if (res != -1) max_w = max(max_w, res + e.w);
        }

    return max_w;
}

int MinimumArea(const int n, const int k, const int s, const Graph &g) {
    ll res = -1;

    for (int v = 0; v < n; ++v)
        res = max(res, Dfs(v, -1, v, k - 1, g));

    return (res == -1) ? -1 : 6 * k * s * s - res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, k, s;

    while (cin >> n >> k >> s, n) {
        vector<Cube> cube(n);
        for (auto &c : cube)
            for (int i = 0; i < 3; ++i) cin >> c.p[i];

        cout << MinimumArea(n, k, s, MakeGraph(n, s, cube)) << '\n';
    }

    return 0;
}