これはシンプルな問題設定で良かった。
http://codeforces.com/contest/965/problem/E
問題
N個の異なる文字列Sが与えられる。
各文字列は末尾を何文字か削ることで短縮できる。
最適な削り方をしたとき、全文字列が異なる範囲で、文字列の総長の最小値を答えよ。
解法
Trie上でマージテクを使う。
まず与えられた文字列でTrieを作り、DFSで葉から順に処理していく。
各頂点では、そこまでをPrefixとして含む文字列について、短縮後の文字列長とそのような文字列数をmap等で持つことにする。
これをマージテクで合わせていこう。
各頂点において、そこを末尾とする文字列がある場合、文字列長をキーとしてmapをインクリメントしよう。
そして解にその文字列長を加算する。あとで短縮する場合はその分を減らす。
さて、短縮後の文字列がみな異なるということは、各頂点を末尾をする文字列を0個または1個生成できることになる。
よって先ほどのmapのうち最長のものを1個選び、現在頂点(に対応する文字列長)に差し替えよう。
ただし、先ほどインクリメントしている、すなわち今の位置を末尾とする文字列がある場合、その文字列自身をmapに追加するため他の文字の長さを削ることはできない。
葉から順にmapをマージしていくので、マージテクで計算量を落とそう。
int N; vector<string> S; int num[101010]; map<int,int> M[101010]; ll ret; const int NUMC=26; class Trie { public: vector<vector<int> > V; int find(string s) { int cur=0; ITR(it,s) if((cur=V[cur][*it+1])==0) return -1; return cur; } void create(vector<string> S) { // 0 is for backtrack V.clear(); V.push_back(vector<int>(NUMC+1)); sort(S.begin(),S.end()); ITR(it,S) { int cur=0; ITR(c,(*it)) { if(V[cur][*c+1]==0) V.push_back(vector<int>(NUMC+1)),V[cur][*c+1]=V.size()-1; cur=V[cur][*c+1]; } } } void dfs(int cur,int depth) { int i; for(int i=1;i<=NUMC;i++) if(V[cur][i]) { int x=V[cur][i]; dfs(x,depth+1); if(M[cur].size()>M[x].size()) swap(M[cur],M[x]); FORR(m,M[x]) M[cur][m.first]+=m.second; } if(num[cur]) { ret+=depth; M[cur][depth]++; } else if(depth && M[cur].size()) { int d=M[cur].rbegin()->first; ret-=d-depth; if(--M[cur][d]==0) M[cur].erase(d); M[cur][depth]++; } } }; Trie T; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>s; FORR(c,s) c-='a'; S.push_back(s); } T.create(S); FOR(i,N) num[T.find(S[i])]++; T.dfs(0,0); cout<<ret<<endl; }
まとめ
これは良い問題だった。