ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, E 解答

E: 3D プリント

問題

3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。

各立方体は0個・1個・2個の立方体と連結することはあるが、3個以上の立方体と連結することはない
ある立方体が2個の立方体と連結するとき、その2つは連結していない
どの2つの立方体も頂点・辺・面で接することはない。真に離れているか、真に共通部分を持つかのどちらかである

解法

連結の関係をグラフに表す。立方体を頂点、連結しているならば辺で結ぶ。
1つ目の条件から頂点の次数は0, 1, または2。これはグラフはパス・サイクル (孤立点) の集合であることが分かる。
2つの立方体が重なったとき、隠れた部分が表面積から引かれる。これは共通部分の直方体の表面積と等しいが、2つ目の条件より、隣り合った立方体の共通部分で過不足なく求められる(共通部分の共通部分などはない)。

コード

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

const LL INF = 1LL<<60;
int N, K, S;
int X[2111], Y[2111], Z[2111];

vector<pair<int, LL> > G[2111]; // (dst, cst)
bool use[2111];

LL intersection(int i, int j) {
    LL x = abs(X[i] - X[j]);
    LL y = abs(Y[i] - Y[j]);
    LL z = abs(Z[i] - Z[j]);

    if (x < S && y < S && z < S) {
	x = min(X[i], X[j]) + S - max(X[i], X[j]);
	y = min(Y[i], Y[j]) + S - max(Y[i], Y[j]);
	z = min(Z[i], Z[j]) + S - max(Z[i], Z[j]);
	return 2 * ( x*y + y*z + z*x );
    } else {
	return 0;
    }
}

LL calc_cost(vector<LL> &c) {
    if ((int)c.size() < K-1) return INF;

    LL sum = (LL)S * S * 6 * K;
    LL ret = INF;

    REP (i, K-1) sum -= c[i];
    amin(ret, sum);

    REP (i, (int)c.size() - K+1) {
	sum += c[i];
	sum -= c[i+K-1];
	amin(ret, sum);
    }
    return ret;
}

int main() {

    while (scanf("%d%d%d", &N, &K, &S), N|K|S) {
	REP (i, N) scanf("%d%d%d", X+i, Y+i, Z+i);


	LL ans = INF;

	REP (i, N) G[i].clear();

	REP (i, N) REP (j, i) {
	   LL cst = intersection(i, j);
	   if (cst > 0) {
	       G[i].push_back(make_pair(j, cst));
	       G[j].push_back(make_pair(i, cst));
	   }
	}

	memset(use, 0, sizeof use);

	REP (i, N) if (!use[i] && (int)G[i].size() <= 1) {

	    int v = i;
	    vector<LL> cst;

	    while (true) {
		use[v] = true;
		int nxt = -1;
		EACH (e, G[v]) if (!use[e->first]) {
		    nxt = e->first;
		    cst.push_back(e->second);
		    break;
		}

		if (nxt == -1) break;
		v = nxt;
	    }

	    if ((int)cst.size() + 1 < K) continue;
	    else amin(ans, calc_cost(cst));
	}

	REP (i, N) if (!use[i]) {
	    int v = i;
	    vector<LL> cst;
	    while (true) {
		use[v] = true;
		int nxt = -1;
		EACH (e, G[v]) if (!use[e->first]) {
		    nxt = e->first;
		    cst.push_back(e->second);
		    break;
		}

		if (nxt == -1) {
		    EACH (e, G[v]) if (e->first == i) {
			cst.push_back(e->second);
			break;
		    }
		    break;
		}
		v = nxt;
	    }

	    if ((int)cst.size() < K) continue;
	    else if ((int)cst.size() == K) {
		LL tmp = (LL)S * S * 6 * K;
		REP (j, cst.size()) tmp -= cst[j];
		amin(ans, tmp);
	    } else {
		cst.insert(cst.end(), cst.begin(), cst.end());
		amin(ans, calc_cost(cst));
	    }
	}

	if (ans == INF) {
	    puts("-1");
	} else {
	    printf("%lld\n", ans);
	}
    }

    return 0;
}