AOJ 2022: Princess, a Cryptanalyst

問題

Princess, a Cryptanalyst | Aizu Online Judge

解法

N! 通りの並び方を試します。で, apple, length の "le" のように前の文字の後半, 後ろの文字の前半で一致しているところがあったら applength のようにつなげて考えればいけます。…と言いたいところなんですがこれでは WA です(これで引っかかりました…)。

apple, pp という文字列があったとすると, apple の中には pp という文字列が含まれているので, applepp とせず, apple と書けば終わりです。こういうのに気を付けて,

same[i][j] = (i 番目の文字の後に j 番目の文字は何文字書かないといけないか。また, そのあと後半に続いている文字は i 番目のものか j 番目のものか) というような配列を作ります。
例えば apple, length の場合は, apple の後に length は後半の 4 文字だけ書けば良いので 「i 番目の文字の後に j 番目の文字は何文字書かないといけないか」というのは 4 です。で, 後半に続いているのは length なので 2 つ目の要素は j です。
一方で apple, pp の場合は, 「i 番目の文字の後に j 番目の文字は何文字書かないといけないか」というのは 0 です。で, pp は apple の途中にあるので, 「そのあと後半に続いている文字は i 番目のものか j 番目のものか)」というのは i です。

よく考えると 1 つ目の要素が j 番目の文字の長さと一致していたら 2 番目の要素は i, とすればよかっただけでした。ﾏｧｲｲﾔ

ICPC は基本的にサンプルが丁寧なイメージですがこれはちょっと厳しかったですね。

pii same[15][15];
char ans[200], tmp[200];
int asize = 0;

// s < t かどうか
bool comp(const char*s, int ssize, const char* t, int tsize) {
	if (ssize < tsize) return true;
	if (ssize > tsize) return false;
	for (int i = 0; i < ssize; i++) {
		if (s[i] < t[i]) return true;
		if (s[i] > t[i]) return false;
	}
	return true;
}

int main() {
    int N;
    while (cin >> N) {
    	if (N==0) break;
    	vector<string> ss(N);
    	for (int i = 0; i < N; i++)
    		cin >> ss[i];
    	for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
    		int sz = min(ss[i].size(), ss[j].size());
    		int maxi = 0;
    		for (int k = 1; k <= sz; k++) {
    			if (ss[i].substr(ss[i].size()-k, k) == ss[j].substr(0, k)) maxi = k;
    		}
    		same[i][j] = pii(maxi, j);
    		for (int k = 0; k < ss[i].size(); k++) {
    			if (ss[i].substr(k, ss[j].size()) == ss[j]) same[i][j] = pii(ss[j].size(), i);
    		}
    	}
    	vector<int> perm(N);
    	for (int i = 0; i < N; i++) 
    		perm[i] = i;
    	bool first = true;
    	do {
    		int sz = 0;
    		for (int i = 0; i < ss[perm[0]].size(); i++) 
    			tmp[i] = ss[perm[0]][i];
    		sz = ss[perm[0]].size();
    		int now = perm[0];
    		for (int i = 0; i < N-1; i++) {
    			int next = perm[i+1];
    			pii p = same[now][next];
    			int len = p.first;
    			for (int j = len; j < ss[next].size(); j++)
    				tmp[sz++] = ss[next][j];
    			now = p.second;
    		}
    		if (first || !comp(ans, asize, tmp, sz)) {
    			asize = sz;
    			for (int i = 0; i < sz; i++)
    				ans[i] = tmp[i];
    		}
    		first = false;
    	} while (next_permutation(perm.begin(), perm.end()));
    	for (int i = 0; i < asize; i++)
    		printf("%c", ans[i]);
    	printf("\n");
    }
    return 0;
}