POJ-1795 : DNA Laboratory

問題概要

A,G,C,Tからなる長さL[i](<100)の文字列がN(<15)個ある。全ての文字列を部分文字列に含むような文字列のなかで辞書順最小のものを求める問題。

解法

ICPC Asia Regionalなどでお馴染みのShortest Super String。他の文字列に包含される文字列を消去した上で巡回セールスマンっぽいのを解けばよい。面倒なのは辞書順最小の構成だけど、これは例によって前から順番に決定していく。その際遷移が有効なものであるかどうかきちんと判定すること。

acceptされたコード

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

const int MAX_N = 15;
const int MAX_L = 100;
const int INF = int(1.05e9); 

int N;
int graph[MAX_N][MAX_N];
int opt[1<<MAX_N][MAX_N];
bool reachable[1<<MAX_N][MAX_N];
string strs[MAX_N];

template<typename numType>
inline bool updateMin(numType& old, const numType& test) {
	if (old > test) {
		old = test;
		return true;
	}
	return false;
}

void init() {
	scanf("%d ", &N);
	char buf[MAX_L + 2];
	for (int i = 0; i < N; ++i) {
		scanf(" %s ", buf);
		strs[i] = string(buf);
	}
}

string solve() {
	sort(strs, strs + N);
	N = unique(strs, strs + N) - strs;

	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) if (i!=j && strs[j].find(strs[i]) != string::npos) {
			strs[i] = strs[j];
		}
	}

	int lens[MAX_N];
	for (int i = 0; i < N; ++i) {
		lens[i] = strs[i].length();
	}

	// (i -> j)
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			for (int l = 0; l <= min(lens[i], lens[j]); ++l) {
				if (strs[i].substr(lens[i] - l) == strs[j].substr(0, l)) {
					graph[i][j] = lens[j] - l;
				}
			}
		}
	}

	for (int bit = 0; bit < 1<<N; ++bit) {
		fill(opt[bit], opt[bit] + N, INF);
	}
	for (int i = 0; i < N; ++i) {
		opt[1<<i][i] = lens[i];
	}
	for (int bit = 0; bit < 1<<N; ++bit) {
		for (int i = 0; i < N; ++i) if (opt[bit][i] != INF) {
			for (int j = 0; j < N; ++j) if (!((bit>>j)&1)) {
				updateMin(opt[bit | (1<<j)][j], opt[bit][i] + graph[i][j]);
			}
		}
	}

	int bestLength = INF;
	for (int i = 0; i < N; ++i) {
		updateMin(bestLength, opt[(1<<N)-1][i]);
	}

	memset(reachable, false, sizeof(reachable));
	for (int i = 0; i < N; ++i) {
		if (opt[(1<<N)-1][i] == bestLength) {
			reachable[(1<<N)-1][i] = true;
		}
	}

	for (int bit = (1<<N) - 1 ; bit >= 0; --bit) {
		for (int i = 0; i < N; ++i) if (reachable[bit][i]) {
			for (int j = 0; j < N; ++j) if (i!=j && ((bit>>j)&1)) {
				reachable[bit &~ (1<<i)][j] |= (opt[bit &~ (1<<i)][j] + graph[j][i] == opt[bit][i]);
			}
		}
	}

	string ans = string(1,'z'+1);
	int appended = 0, last = -1;
	for (int i = 0; i < N; ++i) {
		if (reachable[1<<i][i] && updateMin(ans, strs[i])) {
			last = i;
		}
	}

	appended |= 1<<last;
	for (int _ = 0; _ < N - 1; ++_) {
		string tmp = string(1, 'z'+1);
		int key = -1;
		for (int i = 0; i < N; ++i) if (!((appended>>i)&1)) {
			if (reachable[appended | (1<<i)][i] && opt[appended][last] + graph[last][i] == opt[appended | (1<<i)][i] && updateMin(tmp, strs[i].substr(lens[i] - graph[last][i]))) {
				key = i;
			}
		}
		last = key;
		appended |= 1<<key;
		ans += tmp;
	}

	return ans;
}

int main() {
	int T; scanf("%d", &T);
	for (int i = 0; i < T; ++i) {
		init();
		printf("Scenario #%d:\n%s\n\n", i+1, solve().c_str());
	}
	return 0;
}