Codeforces #288 Div2 D. Tanya and Password

これは知らなかった。
http://codeforces.com/contest/508/problem/D

問題

(N+2)文字のパスワードがある。
このパスワードから生成される、N通りすべての連続した３文字の部分文字列が与えられる。

元のパスワードとして成り立つものが存在すればそれを答えよ。

解法

文字２文字が頂点に対応するようなグラフを考える。
３文字の部分列は辺に相当し、abcという単語は頂点abとbcをつなぐ辺だと考える。

ここまでは自力でたどり着けたが、この後は自力で解けなかったので他の回答を参考。

後はこのグラフのオイラー路を求めればよい。以下のサイトが参考になる。
Spaghetti Source - 有向オイラー路

int N;
int S[201000];
const char* ss="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

int in[64*64],out[64*64];
int num[64*64*64];
string R;

void dfs(int cur) {
	int i;
	FOR(i,64) {
		while(num[cur*64+i]) {
			num[cur*64+i]--;
			dfs(cur%64*64+i);
		}
	}
	R+=ss[cur%64];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>s;
		S[i]=(lower_bound(ss,ss+62,s[0])-ss)*64*64;
		S[i]+=(lower_bound(ss,ss+62,s[1])-ss)*64;
		S[i]+=(lower_bound(ss,ss+62,s[2])-ss);
		num[S[i]]++;
		in[S[i]/64]++;
		out[S[i]%(64*64)]++;
	}
	
	int st=-1;
	FOR(i,64*64) {
		if(in[i]==out[i]) continue;
		else if(in[i]==out[i]+1) {
			if(st!=-1) return _P("NO\n");
			st=i;
		}
		else if(in[i]+1==out[i]) continue;
		else return _P("NO\n");
	}
	
	if(st==-1) FOR(i,64*64) if(in[i]) st=i;
	
	dfs(st);
	R+=ss[st/64];
	reverse(R.begin(),R.end());
	if(R.size()!=N+2) return _P("NO\n");
	
	cout<<"YES"<<endl;
	cout<<R<<endl;
}

まとめ

オイラー路のアルゴリズム知らなかったからしょうがないね…。