TopCoderOpen 2021 Wildcard Elimination Final : Medium ManhattanSnowPlow

こちらはすんなり行った。
https://community.topcoder.com/stat?c=problem_statement&pm=17128&rd=18798

問題

R*Cのグリッドグラフを考える。
各辺を最低1回以上たどるようなパスのうち、最短パスを構築せよ。
なお、始点・終点はどこでも良いし、同じ辺を複数回たどってもよい。

解法

次数が3の点が2個以下にできれば、あとはオイラー路をたどるだけで良い。

• RもCも偶数の場合
  • 次数3の点は、最上段と最下段に(C-2)個、最左列と最右列に(R-2)個ずつある。
  • そこで、隣接する次数3の点でペアを組み、間に辺を1個増やそう。ただし、1ペアだけは増やさなくて良い。
• Rが偶数でCが奇数の場合
  • 上記と同様だが、最上段と最下段に1個ずつ次数3の点を余らせておいてよい。
• Rが奇数でCが偶数の場合
  • 上記と同様だが、最上段と最下段に1個ずつ次数3の点を余らせておいてよい。
• RもCも奇数の場合
  • 「隣接する次数3の点の間に辺を1個増やそう」とすると、最上段・最下段・最左列・最右列に1個ずつペアが組めない点が残る。
  • そこで、最下段で右から2列目の点と、最右列で下から2段目の点の間に追加で辺を張ろう

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath(int root=-1) { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0;
		FOR(i,MV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		//閉路なら奇数を許容しないようにしておく
		if(odd!=0 && odd!=2) return false;
		if(root==-1) {
			root=odd?fo:0;
		}
		else {
			if(odd==2&&E[root].size()%2==0) return false;
		}
		dfs(root);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

UndirectedEulerPath<101000> uep;

class ManhattanSnowPlow {
	public:
	string plow(int H, int W) {
		UndirectedEulerPath<50*50> uep;
		
		int y,x;
		FOR(y,H) FOR(x,W-1) uep.add_path(y*W+x,y*W+x+1);
		FOR(y,H-1) FOR(x,W) uep.add_path(y*W+x,y*W+x+W);
		vector<pair<int,int>> cand;
		for(x=1;x+1<W-1;x+=2) {
			cand.push_back({0*W+x,0*W+x+1});
			cand.push_back({(H-1)*W+x,(H-1)*W+x+1});
		}
		for(y=1;y+1<H-1;y+=2) {
			cand.push_back({y*W+0,(y+1)*W+0});
			cand.push_back({y*W+W-1,(y+1)*W+W-1});
		}
		if(H%2==0&&W%2==0) {
			if(cand.size()) cand.pop_back();
		}
		else if(H%2&&W%2) {
			cand.push_back({(H-1)*W+(W-2),(H-1)*W+(W-1)});
			cand.push_back({(H-2)*W+(W-1),(H-1)*W+(W-1)});
		}
		FORR(c,cand) uep.add_path(c.first,c.second);
		
		assert(uep.GetPath());
		string S;
		int i;
		FOR(i,uep.path.size()-1) {
			if(uep.path[i]-uep.path[i+1]==1) S+="E";
			if(uep.path[i]-uep.path[i+1]==-1) S+="W";
			if(uep.path[i]-uep.path[i+1]==W) S+="N";
			if(uep.path[i]-uep.path[i+1]==-W) S+="S";
		}
		return S;
	}
}

まとめ

割とすんなり思いついたけど、コーディングが若干めんどい。