問題概要

長さ20文字以下の都市の名前が最大14個与えられる．これらのすべてを部分文字列として含むような文字列の長さを求める．

解法概要

与えられた都市の名前の個数をnとする．また，都市の名前の長さの最大値をlとする．

dp[すでに使った都市の集合のbit表現][最後に使った都市]というDPテーブルを埋めていくbit DP．DPテーブルを埋める部分の計算量は，DPテーブルの各要素に格納すべき値が $ O( 1 )$ で求まるなら $ O( 2^n n^2 )$ ．

DPテーブルの各要素の値を $ O( 1 )$ で求めるには，任意の2つの都市i,jについてiの名前のsuffixとjの名前のprefixのかぶっている部分の長さの最大値がわかっている必要がある．これを求める処理は $ O( l \times n^2 )$．

よって全体では1クエリあたり$ O( 2^n n^2 )$ ．

1つだけ注意しなければならないのは，ある都市iの名前が別の都市jの名前の部分文字列となる場合である．この場合，別にjが全体の文字列の先頭や末尾に来ていなくても，jを使いさえしていれば自動的にiも使われていることになるので，このような都市iを残しておくとDPテーブルを埋める処理がうまくかなくなる．したがって，suffixとprefixの "かぶり" の長さを計算する処理やDPテーブルを埋める処理の前に，このような都市iは削除しておく．

ソースコード

#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<vector>
#include<numeric>
 
#define debug(x) cerr << #x << ": " << x << endl
 
using namespace std;
 
int n;
 
int solve(vector<string> cities){
    int merged[n+1][n+1];
    fill_n(merged[0], (n+1)*(n+1), 0);
 
    int length[n+1];
    fill_n(length, n+1, 0);
    for(int i=0;i<n;i++) length[i] = cities[i].length();
 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i == j){
                merged[i][i] = cities[i].length();
            }else{
                bool flag = false;
                 
                // iの後ろにjをくっつける
                int k_max = 0, k_tmp = 0;
                while(k_tmp <= min(length[i], length[j])){
                    flag = true;
                    for(int k=0;k<k_tmp;k++){
                        if(cities[i][length[i]-k_tmp+k] != cities[j][k]){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) k_max = k_tmp;
                    k_tmp++;
                }
                merged[i][j] = k_max;
            }
        }
    }
 
    int dp[1<<n][n];
    fill_n(dp[0], (1<<n)*n, accumulate(length, length+n, 0));
    dp[0][n] = 0;
    for(int c=0;c<n;c++){
        dp[1 << c][c] = length[c];
    }
    for(int i=1;i<(1 << n);i++){
        for(int j=0;j<n;j++){
            for(int c=0;c<n;c++){
                if(i & (1 << c)) continue;
                int nxt = i | (1 << c);
                dp[nxt][c] = min(dp[nxt][c], dp[i][j] + length[c] - merged[j][c]);
            }
        }
    }
 
    return *min_element(dp[(1<<n)-1], dp[(1<<n)-1]+n);
}
 
vector<string> preprocess(vector<string> cities){
    int length[n];
    for(int i=0;i<n;i++) length[i] = cities[i].length();
    // 他の都市jの部分文字列になっている都市iは削除
    vector<string> ret;
    bool flag;
    int m = 0;
    for(int i=0;i<n;i++){
        flag = false;
        for(int j=0;j<n;j++){
            if(i == j) continue;
            if(length[i] > length[j]) continue;
            for(int k=0;k<length[j]-length[i]+1;k++){
                if(cities[j].substr(k, length[i]) == cities[i]){
                    flag = true;
                    break;
                }
            }
            if(flag) break;
        }
        if(!flag){
            ret.push_back(cities[i]);
            m++;
        }
    }
 
    n = m;
    return ret;
}
 
int main(void){
    while(scanf("%d", &n) && n){
        vector<string> cities(n);
        for(int i=0;i<n;i++) cin >> cities[i];
        cout << solve(preprocess(cities)) << endl;
    }
}

NoiminのNoise

ICPCアジア地区予選 2011 F - City Merger

問題概要

解法概要

ソースコード

所感