CSAcademy Round #48 : E. Matching Substrings

手間取ったと思ったけどなんか1位だった。
https://csacademy.com/contest/round-48/task/matching-substrings/

問題

N個のK文字の文字列S[i]が与えられる。

N+K-1文字の文字列からは、K文字の部分文字列はN通り取得することができる。
このN通りが、入力の文字列群と一致するような(N+K-1)文字の文字列を構成せよ。

解法

K==1のときは、入力を連結して出力するだけでよい。
構成する(N+K-1)文字の文字列中で、ある(末尾以外の)K文字を考える。
1文字後ろにスライドした位置のK文字も入力のN文字列内に含まれなければいけない。

そこで、各文字列について(K-1)文字のprefixおよび(K-1)文字のsuffixに相当する最大2N個の頂点からなる有向グラフを考える。
prefix/suffixが等しいものが複数出る場合、それらの頂点は同一とみなす。
各文字列について、prefixに相当する頂点からsuffixに相当する頂点に有向辺を張ろう。

このグラフにおいて、題意を満たす文字列はこの有向グラフにおけるオイラーパスに相当すると考えることができる。
よってオイラーパスを求めて(N+K-1)文字の文字列を復元すれば終了。

int N,K,V;
string S[101010];
map<string,int> M;
string T[202020];
int A[101010],B[101010];

template<int MV> class DirectedEulerPath {
public:
	int NV;
	vector<int> path;
	vector<int> E[MV];
	void add_path(int x,int y) { E[x].push_back(y);}
	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int e=E[cur].back();
			E[cur].pop_back();
			dfs(e);
		}
		path.push_back(cur);
	}
	
	bool GetPath() {
		assert(NV);
		int te=0,i;
		vector<int> deg(NV);
		FOR(i,NV) {
			te += E[i].size();
			deg[i]+=E[i].size();
			FORR(e,E[i]) deg[e]--;
		}
		int d0=0,s=0;
		FOR(i,NV) {
			if(deg[i]>1 || deg[i]<-1) return false;
			if(deg[i]==0) d0++;
			if(deg[i]==1) s=i;
		}
		if(d0!=NV && d0+2!=NV) return false;
		dfs(s);
		reverse(path.begin(),path.end());
		return path.size()==te+1;
	}
};

DirectedEulerPath<202020> dep;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>S[i];
	
	if(K==1) {
		FOR(i,N) cout<<S[i];
		cout<<endl;
		return;
	}
	
	FOR(i,N) M[S[i].substr(0,K-1)]=M[S[i].substr(1,K-1)]=0;
	x=0;
	FORR(r,M) T[x]=r.first, r.second=x++;
	
	V=M.size();
	dep.init(V);
	FOR(i,N) {
		A[i]=M[S[i].substr(0,K-1)];
		B[i]=M[S[i].substr(1,K-1)];
		dep.add_path(A[i],B[i]);
	}
	if(!dep.GetPath()) return _P("-1\n");
	
	string ret=T[dep.path[0]];
	for(i=1;i<dep.path.size();i++) ret+=T[dep.path[i]].back();
	cout<<ret<<endl;
	
	
	
}

まとめ

有向グラフのオイラーパスライブラリ持ってなかったので手間取った。