kmjp's blog

競技プログラミング参加記です

Codeforces #476 Div2 E. Short Code

これはシンプルな問題設定で良かった。
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;
}

まとめ

これは良い問題だった。