TopCoderOpen 2020 Round4 : Hard BigJump

うーん。
https://community.topcoder.com/stat?c=problem_statement&pm=16143&rd=18191

問題

正偶数Nが与えられる。
0～(N-1)のラベルを持つ頂点が順に並んでいるとする。
xのラベルを持つ点から、(2*x)%N及び(2*x-1)%Nのラベルを持つ点に有向辺があるとする。
全頂点を1回ずつたどる閉路があればそれを答えよ。

解法

N=2Kとする。xとx+Kからの行ける先は同じなので、両者の行き先は必ず異なることになる。
そこで0～(K-1)のラベルをもつK頂点からなるグラフを考えよう。
各点xからは、(2*x)%Kと(2*x-1)%Kに遷移できるとする。
このグラフでオイラーパスを求めると、元のグラフでちょうど各点2回ずつたどることになり結果的に元のグラフのハミルトンパスを求められる。

N=2の時だけはこの方法だとうまくいかないが、経路は{0,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 BigJump {
	public:
	vector <int> construct(int N) {
		int i;
		if(N==2) return {0,1};
		DirectedEulerPath<2020> dep;
		dep.init(N/2);
		FOR(i,N/2) {
			dep.add_path(i,i*2%(N/2));
			dep.add_path(i,(i*2+N-1)%(N/2));
		}
		assert(dep.GetPath());
		vector<int> V,P=dep.path;
		int cur=0;
		V.push_back(0);
		for(i=1;i<N;i++) {
			if(cur*2%N==P[i]) cur=P[i];
			else if(cur*2%N==P[i]+(N/2)) cur=P[i]+(N/2);
			else if((cur*2+N-1)%N==P[i]) cur=P[i];
			else if((cur*2+N-1)%N==P[i]+(N/2)) cur=P[i]+(N/2);
			V.push_back(cur);
		}
		cout<<endl;
		
		
		
		return V;
		
		
		
	}
}

まとめ

半分に折りたたむことは考えたんだけどな…。