yukicoder : No.1166 NADA DNA

問題文の意味を考え直すと簡単になる問題。
https://yukicoder.me/problems/no/1166

問題

N個の同じ長さの文字列が与えられる。
ここで、二分木を形成し、その葉に各文字列を割り当てたとする。
葉以外のノードのコストは、左右両子ノードの先にある文字列を1つずつ取り出したとき、そのハミング距離の最小値とする。

最適な二分木を形成すると、ノードの総コストはいくつか。

解法

これは二分木とあるが、実質最小全域木を作ってしまって問題ない。
そこで先に全文字列対のハミング距離を求め、最小全域木を作ればよい。

int N,L;
string G[1010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>G[i];
	
	vector<vector<int>> E;
	FOR(y,N) FOR(x,y) {
		j=0;
		FOR(i,L) j+=G[x][i]!=G[y][i];
		E.push_back({j,x,y});
	}
	
	sort(ALL(E));
	int ret=0;
	FORR(e,E) {
		if(uf[e[1]]!=uf[e[2]]) {
			uf(e[1],e[2]);
			ret+=e[0];
		}
	}
	cout<<ret<<endl;
	
}

まとめ

二分木にこだわると苦労する問題。