お姫様の暗号解読 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022

aoj2022.cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) for(auto x : v){cout << x << " ";} cout << endl
#define printVS(vs) for(auto x : vs){cout << x << endl;}
#define printVV(vv) for(auto v : vv){for(auto&& x : v){cout << x << " ";}cout << endl;}
#define printP(p) cout << p.first << " " << p.second << endl
#define printVP(vp) for(auto p : vp) printP(p);

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<Pii> vp;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

int n;
vector<string> s;
vvi d;
vvi dp;

int common(string s, string t) {
    for (int k = min(s.size(), t.size()); k >= 0; k--) {
        if (s.substr((int)s.size() - k) == t.substr(0, k)) {
            return k;
        }
    }
}

string concat(string s, string t) {
    int k = common(s, t);
    return s + t.substr(k);
}

string mymin(string s, string t) {
    if (s.size() < t.size()) return s;
    if (s.size() > t.size()) return t;
    return s < t ? s : t;
}

string dfs(int state, int j, string str) {
    if (__builtin_popcount(state) == 1) return concat(s[j], str);

    string ret(101, 'z');
    rep(i, n) {
        if (!((state >> i) & 1)) continue;
        if (dp[state - (1 << j)][i] + d[i][j] == dp[state][j]) {
            ret = mymin(ret, dfs(state - (1 << j), i, concat(s[i], str)));
        }
    }

    return ret;
}



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

    int t = 0;
    while (cin >> n, n) {
        s.clear();
        s.resize(n);
        rep(i, n) cin >> s[i];

        vector<bool> alive(n, true);
        rep(i, n) {
            rep2(j, i + 1, n) {
                if (s[i] == s[j]) {
                    alive[j] = false;
                }
            }
        }
        rep(i, n) {
            rep(j, n) {
                if (i == j) continue;
                if (s[i] != s[j] && s[i].find(s[j]) != string::npos) {
                    alive[j] = false;
                }
            }
        }

        {
            vector<string> t;
            rep(i, n) {
                if (alive[i]) {
                    t.emplace_back(s[i]);
                }
            }
            s = t;
            n = s.size();
        }

        d.clear();
        d.resize(n, vi(n));
        rep(i, n) {
            rep(j, n) {
                if (i == j) continue;
                d[i][j] = common(s[i], s[j]);
            }
        }

        dp.clear();
        dp.resize(1 << n, vi(n, -1));
        rep(i, n) {
            dp[1 << i][i] = 0;
        }
        rep(state, 1 << n) {
            rep(i, n) {
                if (dp[state][i] == -1) continue;
                rep(j, n) {
                    if ((state >> j) & 1) continue;
                    dp[state | (1 << j)][j] = max(dp[state | (1 << j)][j], dp[state][i] + d[i][j]);
                }
            }
        }

        int mx = *max_element(all(dp[(1 << n) - 1]));
        string ans(101, 'z');
        rep(j, n) {
            if (dp[(1 << n) - 1][j] == mx) {
                ans = mymin(ans, dfs((1 << n) - 1, j, s[j]));
            }
        }
        cout << ans << endl;
    }

}