TopCoder SRM 852 : Div1 Medium MergingNumbers

凡ミスを重ねてミスしたもったいない問題。
https://community.topcoder.com/stat?c=problem_statement&pm=18150

問題

3桁以上の2つの整数値をマージするとは、片方の末尾の3桁ともう片方の先頭の3桁が一致する場合、前者の後に後者の上から4桁目以降の数字を並べた整数値を作ることである。

N個の整数が与えられる。
ここに0個または1個整数を追加し、全部の整数をマージできるか。
できるなら追加する整数を求めよ。

解法

N=1の場合、追加不要でマージ可能。
Nが2以上の場合、3桁未満の整数があるとそれはマージできないので、マージ不可。

そうでない場合、000～999に相当する1000頂点のグラフを考える。
整数Xがあったとき、頭3桁から末尾3桁に相当する辺を追加しよう。
このグラフに1辺足してオイラー閉路を作れればよいことになる。
追加する辺の候補は多くないので、愚直に試すとよい。

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;
	}
};

class MergingNumbers {
	public:
	vector<int> Vs;
	DirectedEulerPath<606> dep;
	int ok(vector<pair<int,int>>& V) {
		dep.init(Vs.size());
		FORR2(a,b,V) dep.add_path(a,b);
		return dep.GetPath();
		
	}
	
	
	
	int solve(vector <int> numbers) {
		int i;
		if(numbers.size()==1) return 0;
		vector<pair<int,int>> V;
		set<int> A,B;
		Vs.clear();
		FORR(a,numbers) {
			if(a<100) return -1;
			int y=a%1000;
			int x=a;
			while(x>=1000) x/=10;
			V.push_back({x,y});
			Vs.push_back(x);
			Vs.push_back(y);
		}
		sort(ALL(Vs));
		Vs.erase(unique(ALL(Vs)),Vs.end());
		FORR2(x,y,V) {
			x=lower_bound(ALL(Vs),x)-Vs.begin();
			y=lower_bound(ALL(Vs),y)-Vs.begin();
			A.insert(x);
			if(Vs[y]>=100) B.insert(y);
		}
		
		if(ok(V)) return 0;
		FORR(a,A) FORR(b,B) {
			V.push_back({b,a});
			if(ok(V)) return Vs[b]*1000+Vs[a];
			V.pop_back();
		}
		return -1;
	}
}

まとめ

落としたのもったいない。