Dilworth の定理から、DAG の最小パス被覆！！ かつて流行った高度典型。
問題概要
個の文字列
が与えられる。各文字列には重み
がついている。
これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満たすようにいくつか抜き出すとき、抜き出した文字列の総和の最大値を求めよ。
制約
- 文字列の長さの総和
考えたこと
グラフの問題として考えると良さそうに思った。そのようなことをすると、問題が一般化されて解けない問題になることもあるので注意が必要だが、今回はグラフの問題にしてよさそうだった。それは、「そのようなグラフになるような文字列」を構築することもできそうに思えたからだった。
さて、今回は 個の文字列から頂点数
の有向グラフを次のようにつくる。文字列
が文字列
に部分文字列として含まれるとき、頂点
から頂点
へと有向辺を貼ることにしよう。
このグラフは「推移閉包をとっても同一な DAG である」という特徴をもつ。つまり、辺 と辺
があるとき、辺
があるという性質を満たすのだ。
そのような DAG では、次の双対性がなりたつ。
推移閉包をとっても同一な DAG において、
最大独立集合 = 最小パス被覆
注意点として、今回は頂点に重みがある。しかし、大して問題ない。それらの頂点を重さの個数だけ分裂させて考えたグラフについて考えることで正当化できる。
DAG の最小パス被覆
DAG の最小パス被覆は、蟻本にも載ってる。下図のように「二部グラフの最大マッチング問題」に帰着される。
左側の DAG は、
- 頂点 0 → 頂点 1 → 頂点 7
- 頂点 4 → 頂点 2 → 頂点 3
- 頂点 6 → 頂点 5
という 3 本のパスで被覆されている。これは右側の二部グラフでは、8 - 3 = 5 本のマッチング辺に対応している。
よくみると、左側の 3 本のパスの始点をなす頂点 0, 4, 6 は、右側の二部グラフでは右側ノードでマッチングの端点になっていない頂点たちに対応している。
そんなわけで、「DAG の最小パス被覆の本数」は「頂点数 - 二部グラフの最大マッチングの本数」に一致する。
まとめ
以上から、この問題は、二部グラフの最大マッチング (頂点に重みあり) へと帰着された。
Dinic 法などを使えば計算量は におさえられる。
コード
グラフを作る部分では、Suffix Array を用いた。
#include <bits/stdc++.h> using namespace std; using pint = pair<int, int>; using pll = pair<long long, long long>; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } // Sparse Table template<class MeetSemiLattice> struct SparseTable { vector<vector<MeetSemiLattice> > dat; vector<int> height; SparseTable() { } SparseTable(const vector<MeetSemiLattice> &vec) { init(vec); } void init(const vector<MeetSemiLattice> &vec) { int n = (int)vec.size(), h = 1; while ((1<<h) < n) ++h; dat.assign(h, vector<MeetSemiLattice>(1<<h)); height.assign(n+1, 0); for (int i = 2; i <= n; i++) height[i] = height[i>>1]+1; for (int i = 0; i < n; ++i) dat[0][i] = vec[i]; for (int i = 1; i < h; ++i) for (int j = 0; j < n; ++j) dat[i][j] = min(dat[i-1][j], dat[i-1][min(j+(1<<(i-1)),n-1)]); } MeetSemiLattice get(int a, int b) { return min(dat[height[b-a]][a], dat[height[b-a]][b-(1<<height[b-a])]); } }; // SA-IS (O(N)) template<class Str> struct SuffixArray { // data Str str; vector<int> sa; // sa[i] : the starting index of the i-th smallest suffix (i = 0, 1, ..., n) vector<int> rank; // rank[sa[i]] = i vector<int> lcp; // lcp[i]: the lcp of sa[i] and sa[i+1] (i = 0, 1, ..., n-1) SparseTable<int> st; // use for calcultating lcp(i, j) // getter int& operator [] (int i) { return sa[i]; } const int& operator [] (int i) const { return sa[i]; } vector<int> get_sa() { return sa; } vector<int> get_rank() { return rank; } vector<int> get_lcp() { return lcp; } // constructor SuffixArray() {} SuffixArray(const Str& str_, bool no_limit_elements = false) : str(str_) { build_sa(no_limit_elements); } void init(const Str& str_, bool no_limit_elements = false) { str = str_; build_sa(no_limit_elements); } void build_sa(bool no_limit_elements = false) { vector<int> s; int num_of_chars = 256; if (!no_limit_elements) { for (int i = 0; i < (int)str.size(); ++i) { s.push_back(str[i] + 1); } } else { unordered_map<int,int> dict; for (int i = 0; i < (int)str.size(); ++i) { if (!dict.count(str[i])) dict[str[i]] = dict.size(); } for (int i = 0; i < (int)str.size(); ++i) { s.push_back(dict[str[i]] + 1); } num_of_chars = (int)dict.size(); } s.push_back(0); sa = sa_is(s, num_of_chars); build_lcp(s); build_sparse_table(); } // SA-IS // num_of_chars: # of characters vector<int> sa_is(vector<int> &s, int num_of_chars) { int N = (int)s.size(); if (N == 0) return {}; else if (N == 1) return {0}; else if (N == 2) { if (s[0] < s[1]) return {0, 1}; else return {1, 0}; } vector<int> isa(N); vector<bool> ls(N, false); for (int i = N - 2; i >= 0; --i) { ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]); } vector<int> sum_l(num_of_chars + 1, 0), sum_s(num_of_chars + 1, 0); for (int i = 0; i < N; ++i) { if (!ls[i]) ++sum_s[s[i]]; else ++sum_l[s[i] + 1]; } for (int i = 0; i <= num_of_chars; ++i) { sum_s[i] += sum_l[i]; if (i < num_of_chars) sum_l[i + 1] += sum_s[i]; } auto induce = [&](const vector<int> &lms) -> void { fill(isa.begin(), isa.end(), -1); vector<int> buf(num_of_chars + 1); copy(sum_s.begin(), sum_s.end(), buf.begin()); for (auto d: lms) { if (d == N) continue; isa[buf[s[d]]++] = d; } copy(sum_l.begin(), sum_l.end(), buf.begin()); isa[buf[s[N - 1]]++] = N - 1; for (int i = 0; i < N; ++i) { int v = isa[i]; if (v >= 1 && !ls[v - 1]) { isa[buf[s[v - 1]]++] = v - 1; } } copy(sum_l.begin(), sum_l.end(), buf.begin()); for (int i = N - 1; i >= 0; --i) { int v = isa[i]; if (v >= 1 && ls[v - 1]) { isa[--buf[s[v - 1] + 1]] = v - 1; } } }; vector<int> lms, lms_map(N + 1, -1); int M = 0; for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms_map[i] = M++; } } lms.reserve(M); for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms.push_back(i); } } induce(lms); if (M) { vector<int> lms2; lms2.reserve(isa.size()); for (auto v: isa) { if (lms_map[v] != -1) lms2.push_back(v); } int rec_upper = 0; vector<int> rec_s(M); rec_s[lms_map[lms2[0]]] = 0; for (int i = 1; i < M; ++i) { int l = lms2[i - 1], r = lms2[i]; int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N; int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N; bool same = true; if (nl - l != nr - r) same = false; else { while (l < nl) { if (s[l] != s[r]) break; ++l, ++r; } if (l == N || s[l] != s[r]) same = false; } if (!same) ++rec_upper; rec_s[lms_map[lms2[i]]] = rec_upper; } auto rec_sa = sa_is(rec_s, rec_upper); vector<int> sorted_lms(M); for (int i = 0; i < M; ++i) { sorted_lms[i] = lms[rec_sa[i]]; } induce(sorted_lms); } return isa; } // find min id that str.substr(sa[id]) >= T int lower_bound(const Str& T) { int left = -1, right = sa.size(); while (right - left > 1) { int mid = (left + right) / 2; if (str.compare(sa[mid], string::npos, T) < 0) left = mid; else right = mid; } return right; } // find min id that str.substr(sa[id], T.size()) > T int upper_bound(const Str& T) { int left = -1, right = sa.size(); while (right - left > 1) { int mid = (left + right) / 2; if (str.compare(sa[mid], T.size(), T) <= 0) left = mid; else right = mid; } return right; } // find min id that sa[id] >= str.substr(l, r-l) int lower_bound(int l, int r) { int left = -1, right = rank[l]; while (right - left > 1) { int mid = (left + right) / 2; if (st.get(mid, rank[l]) < r - l) left = mid; else right = mid; } return right; } // search bool is_contain(const Str& T) { int lb = lower_bound(T); if (lb >= sa.size()) return false; return str.compare(sa[lb], T.size(), T) == 0; } // find lcp void build_lcp(const vector<int> &s) { int N = (int)s.size(); rank.assign(N, 0), lcp.assign(N - 1, 0); for (int i = 0; i < N; ++i) rank[sa[i]] = i; int h = 0; for (int i = 0; i < N - 1; ++i) { int pi = sa[rank[i] - 1]; if (h > 0) --h; for (; pi + h < N && i + h < N; ++h) { if (s[pi + h] != s[i + h]) break; } lcp[rank[i] - 1] = h; } } // build sparse table for calculating lcp void build_sparse_table() { st.init(lcp); } // calc lcp of str.sutstr(a) and str.substr(b) int get_lcp(int a, int b) { return st.get(min(rank[a], rank[b]), max(rank[a], rank[b])); } // debug void dump() { for (int i = 0; i < sa.size(); ++i) { cout << i << ": " << sa[i] << ", " << str.substr(sa[i]) << endl; } } }; // edge class (for network-flow) template<class FLOWTYPE> struct FlowEdge { // core members int rev, from, to; FLOWTYPE cap, icap, flow; // constructor FlowEdge(int r, int f, int t, FLOWTYPE c) : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {} void reset() { cap = icap, flow = 0; } // debug friend ostream& operator << (ostream& s, const FlowEdge& E) { return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')'; } }; // graph class (for network-flow) template<class FLOWTYPE> struct FlowGraph { // core members vector<vector<FlowEdge<FLOWTYPE>>> list; vector<pair<int,int>> pos; // pos[i] := {vertex, order of list[vertex]} of i-th edge // constructor FlowGraph(int n = 0) : list(n) { } void init(int n = 0) { list.assign(n, FlowEdge<FLOWTYPE>()); pos.clear(); } // getter vector<FlowEdge<FLOWTYPE>> &operator [] (int i) { return list[i]; } const vector<FlowEdge<FLOWTYPE>> &operator [] (int i) const { return list[i]; } size_t size() const { return list.size(); } FlowEdge<FLOWTYPE> &get_rev_edge(const FlowEdge<FLOWTYPE> &e) { if (e.from != e.to) return list[e.to][e.rev]; else return list[e.to][e.rev + 1]; } FlowEdge<FLOWTYPE> &get_edge(int i) { return list[pos[i].first][pos[i].second]; } const FlowEdge<FLOWTYPE> &get_edge(int i) const { return list[pos[i].first][pos[i].second]; } vector<FlowEdge<FLOWTYPE>> get_edges() const { vector<FlowEdge<FLOWTYPE>> edges; for (int i = 0; i < (int)pos.size(); ++i) { edges.push_back(get_edge(i)); } return edges; } // change edges void reset() { for (int i = 0; i < (int)list.size(); ++i) { for (FlowEdge<FLOWTYPE> &e : list[i]) e.reset(); } } void change_edge(FlowEdge<FLOWTYPE> &e, FLOWTYPE new_cap, FLOWTYPE new_flow) { FlowEdge<FLOWTYPE> &re = get_rev_edge(e); e.cap = new_cap - new_flow, e.icap = new_cap, e.flow = new_flow; re.cap = new_flow; } // add_edge void add_edge(int from, int to, FLOWTYPE cap) { pos.emplace_back(from, (int)list[from].size()); list[from].push_back(FlowEdge<FLOWTYPE>((int)list[to].size(), from, to, cap)); list[to].push_back(FlowEdge<FLOWTYPE>((int)list[from].size() - 1, to, from, 0)); } // debug friend ostream& operator << (ostream& s, const FlowGraph &G) { const auto &edges = G.get_edges(); for (const auto &e : edges) s << e << endl; return s; } }; // Dinic template<class FLOWTYPE> FLOWTYPE Dinic (FlowGraph<FLOWTYPE> &G, int s, int t, FLOWTYPE limit_flow) { FLOWTYPE current_flow = 0; vector<int> level((int)G.size(), -1), iter((int)G.size(), 0); // Dinic BFS auto bfs = [&]() -> void { level.assign((int)G.size(), -1); level[s] = 0; queue<int> que; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (const FlowEdge<FLOWTYPE> &e : G[v]) { if (level[e.to] < 0 && e.cap > 0) { level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } } }; // Dinic DFS auto dfs = [&](auto self, int v, FLOWTYPE up_flow) { if (v == t) return up_flow; FLOWTYPE res_flow = 0; for (int &i = iter[v]; i < (int)G[v].size(); ++i) { FlowEdge<FLOWTYPE> &e = G[v][i], &re = G.get_rev_edge(e); if (level[v] >= level[e.to] || e.cap == 0) continue; FLOWTYPE flow = self(self, e.to, min(up_flow - res_flow, e.cap)); if (flow <= 0) continue; res_flow += flow; e.cap -= flow, e.flow += flow; re.cap += flow, re.flow -= flow; if (res_flow == up_flow) break; } return res_flow; }; // flow while (current_flow < limit_flow) { bfs(); if (level[t] < 0) break; iter.assign((int)iter.size(), 0); while (current_flow < limit_flow) { FLOWTYPE flow = dfs(dfs, s, limit_flow - current_flow); if (!flow) break; current_flow += flow; } } return current_flow; }; template<class FLOWTYPE> FLOWTYPE Dinic(FlowGraph<FLOWTYPE> &G, int s, int t) { return Dinic(G, s, t, numeric_limits<FLOWTYPE>::max()); } int main() { // 同一文字列は、スコアが最大のもののみを残して除外する int N; cin >> N; vector<string> nS(N); vector<long long> nA(N); map<string, long long> ma; for (int i = 0; i < N; ++i) cin >> nS[i]; for (int i = 0; i < N; ++i) cin >> nA[i]; for (int i = 0; i < N; ++i) chmax(ma[nS[i]], nA[i]); N = ma.size(); vector<int> pl(N, 0); vector<string> S(N); vector<long long> A(N, 0); string T = ""; int iter = 0; for (auto [str, val] : ma) { pl[iter] = T.size(); S[iter] = str; A[iter] = val; T += str + "$"; ++iter; } // Suffix Array を用いてグラフを構築する SuffixArray<string> sa(T); FlowGraph<long long> G(N * 2 + 2); int s = N * 2, t = N * 2 + 1; const long long INF = 1LL<<50; for (int i = 0; i < N; ++i) { G.add_edge(s, i, A[i]); G.add_edge(i + N, t, A[i]); } set<pint> alr; for (int i = 0; i < N; ++i) { for (int j = 0; j < T.size(); ++j) { if (sa.get_lcp(pl[i], j) >= S[i].size()) { int v = upper_bound(pl.begin(), pl.end(), j) - pl.begin() - 1; if (v < 0 || v == i) continue; if (!alr.count(pint(i, v))) G.add_edge(i, v + N, INF); } } } // 答え long long sum = 0, max_flow = Dinic(G, s, t); for (int i = 0; i < N; ++i) sum += A[i]; cout << sum - max_flow << endl; }
