fuqinho@競技プログラミング

コンテストやオンラインジャッジで出題されたクイズを頑張って解きます

POJ 1795 - DNA Laboratory

概要

N個の文字列が与えられる。それらの文字列を全て含む文字列のうち、最短のものを求めよ。同じ長さの解が複数ある場合は辞書順最小のものを答えよ。(原文)

制約

  • N ≦ 15

解法

  • まず、どれかの文字列に完全に含まれてしまう文字列は、あっても無くても同じなので省く。
  • 残った文字列を連結すれば、全てを含む文字列が出来る。ただし連結部分では共通部分をまとめる。
  • 状態(S, i)を、「集合Sに含まれる文字列が連結済みで、最後がi番目の文字列になっている状態」とし、それぞれの状態における最短の文字列長をビットDPで求める。
  • 最短の長さが求まるので、逆にたどって最短解にたどり着き得る状態がどれかチェックしておく。
  • 上記の情報を利用して、深さ優先探索で文字列を復元し、最適解を更新していく。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// Limit: 30000K  5000ms
// Used :  3132K  2016ms
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int INF = 1000000000;
const int MAX_N = 15;

int common[MAX_N][MAX_N];
int dp[1 << MAX_N][MAX_N];
bool ok[1 << MAX_N][MAX_N];

vector<string> remove_ignorable_strings(vector<string>& S) {
  vector<bool> can_remove(S.size());
  for (int i = 0; i < S.size(); i++) {
    for (int j = 0; j < S.size(); j++) {
      if (i != j) {
        if (!can_remove[i] && S[i].find(S[j]) != string::npos) {
          can_remove[j] = true;
        }
      }
    }
  }
  vector<string> res;
  for (int i = 0; i < S.size(); i++) {
    if (!can_remove[i]) res.push_back(S[i]);
  }
  return res;
}

int common_part(string& s_head, string& s_tail) {
  for (int i = 0; i < s_head.size(); i++) {
    if (s_head[i] == s_tail[0]) {
      string s = s_head.substr(i);
      if (s_tail.find(s) == 0) {
        return s.size();
      }
    }
  }
  return 0;
}

void calc_common_part(vector<string>& S) {
  memset(common, 0, sizeof(common));
  for (int i = 0; i < S.size(); i++) {
    for (int j = 0; j < S.size(); j++) {
      if (i != j) {
        common[i][j] = common_part(S[i], S[j]);
      }
    }
  }
}

void dfs(int state, int last, string cur, string& best, vector<string>& S) {
  if (state == (1 << S.size()) - 1) {
    if (cur < best) best = cur;
    return;
  }

  for (int i = 0; i < S.size(); i++) {
    if ((state & (1<<i)) == 0 && ok[state|(1<<i)][i]) {
      if (dp[state][last] + S[i].size() - common[last][i] == dp[state|(1<<i)][i]) {
        string s = cur + S[i].substr(common[last][i]);
        if (s < best) dfs(state|(1<<i), i, s, best, S);
      }
    }
  }
}

string solve(int N, vector<string>& S) {
  // 他の文字列に完全に含まれてる文字列はあっても無くても同じなので消す
  // 深さ優先探索する時の効率化のために、辞書順でソートしておく.
  S = remove_ignorable_strings(S);
  sort(S.begin(), S.end());
  N = S.size();

  // common[i][j]: S[i]の後ろにS[j]を繋げた場合の共通部分の長さ
  // 後の計算でよく使うので事前計算しておく。
  calc_common_part(S);

  // dp[S][i]: Sに含まれる文字列を繋げて最後がS[i]になっている場合の最短の長さ
  for (int i = 0; i < (1<<N); i++) {
    for (int j = 0; j < N; j++) dp[i][j] = INF;
  }
  for (int i = 0; i < N; i++) dp[(1 << i)][i] = S[i].size();

  // bit DPして各状態の最短の長さを求めておく
  for (int s = 0; s < (1 << N); s++) {
    for (int i = 0; i < N; i++) if (dp[s][i] != INF) {
      for (int j = 0; j < N; j++) if ((s & (1 << j)) == 0) {
        int next_s = (s | (1<<j));
        dp[next_s][j] = min(dp[next_s][j],
                            dp[s][i] + (int)S[j].size() - common[i][j]);
      }
    }
  }

  // 答えになる文字列の長さが求まる。残りは文字列を復元する作業
  int min_length = INF;
  for (int i = 0; i < N; i++) min_length = min(min_length, dp[(1<<N)-1][i]);

  // ok[s][i]: sに含まれる文字列を連結して最後がiになっている状態が、
  // 最適解への経路になり得る場合はtrueにする
  memset(ok, 0, sizeof(ok));
  for (int i = 0; i < N; i++) {
    if (dp[(1<<N)-1][i] == min_length) ok[(1<<N)-1][i] = true;
  }
  for (int s = (1<<N)-1; s >= 0; s--) {
    for (int i = 0; i < N; i++) if (ok[s][i]) {
      for (int j = 0; j < N; j++) if (i != j && (s & (1<<i))) {
        if (dp[s & ~(1<<i)][j] == dp[s][i] - S[i].size() + common[j][i]) {
          ok[s & ~(1<<i)][j] = true;
        }
      }
    }
  }

  // 辞書順で最も小さい解を深さ優先探索で求める
  string best = "Z";
  for (int i = 0; i < N; i++) {
    if (ok[1<<i][i]) dfs(1<<i, i, S[i], best, S);
  }
  return best;
}

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

  int T; cin >> T;
  for (int t = 0; t < T; t++) {
    int N; cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    string ans = solve(N, S);
    cout << "Scenario #" << t+1 << ":\n" << ans << endl << endl;
  }
}