Facebook Hacker Cup 2016 Qualification Round Text Editor

問題

https://www.facebook.com/hackercup/problem/1525154397757404/

解法

まず, 前準備として ある文字列から別の文字列に変換する際に必要なコストを計算します。これは, それぞれの suffix がどこまで一致しているかを調べることで求められます。

また, suffix でコストが決まることを考えると, 文字列を作る順番は, 辞書順にすることが有利です。

ということで, dp[now][num] = (now 個目までの文字列までで num 個の文字を print した時の, 操作の最小回数) という dp を考えれば, 答えを求められます。

const int MAXN = 333;
const int INF = 1e9;
string dict[MAXN];
int N, K;
int dp[MAXN][MAXN];
int dist[MAXN][MAXN];

int dfs(int now, int num) {
    int& ret = dp[now][num];
    if (ret >= 0) return ret;
    if (num == K) return ret = (int)dict[now].size();
    ret = INF;
    for (int i = now+1; i < N; i++) {
        ret = min(ret, dist[now][i] + dfs(i, num+1));
    }
    return ret;
}

void solve(int T) {
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> dict[i];
    sort(dict, dict+N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int len = min(dict[i].size(), dict[j].size());
            int k;
            for (k = 0; k < len; k++) {
                if (dict[i][k] != dict[j][k]) break;
            }
            dist[i][j] = dict[i].size()-k + dict[j].size()-k;
        }
    }
    int ans = INF;
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < N; i++) ans = min<int>(ans, dict[i].size()+dfs(i, 1));
    cout << "Case #" << T << ": " << ans+K << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}