CodeQUEEN 2025 決勝 : H - ライブ

なるほど…。
https://atcoder.jp/contests/codequeen2025-final-Public/tasks/codequeen2025_final_h

問題

整数H,Wが与えられる。
H*Wのグリッドの辺からなる(H+1)*(W+1)点のグラフを考える。
各辺を1回以上通る閉路のうち最短のものを求めよ。

解法

H,Wが大きいと、次数が奇数となる点が複数現れ、一筆書きはできないことがわかる。
そこで、次数が奇数となる点について、距離が近いもの同士をペアにして間に辺を張ろう(多重辺ができてもよい)。
そうすれば各点の次数が偶数になるので、オイラー閉路が作れる。

template<int MV> class UndirectedEulerPath {
public:
	int NV;
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }

	
	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 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;
		assert(NV);
		FOR(i,NV) {
			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) {
			if(odd) {
				root=fo;
			}
			else {
				FOR(i,NV) if(E[i].size()) root=i;
			}
		}
		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<101*101> uep;
int H,W;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	H++,W++;
	uep.init(H*W);
	FOR(y,H) FOR(x,W) {
		if(x+1<W) uep.add_path(y*W+x,y*W+x+1);
		if(y+1<H) uep.add_path(y*W+x,(y+1)*W+x);
	}
	vector<int> cand;
	for(x=1;x<W-1;x++) cand.push_back(x);
	for(y=1;y<H-1;y++) cand.push_back(y*W+(W-1));
	for(x=W-2;x>=1;x--) cand.push_back((H-1)*W+x);
	for(y=H-2;y>=1;y--) cand.push_back(y*W);
	FOR(i,cand.size()/2) uep.add_path(cand[i*2],cand[i*2+1]);
	uep.GetPath(0);
	
	string S;
	FOR(i,uep.path.size()-1) {
		int cy=uep.path[i]/W;
		int cx=uep.path[i]%W;
		int ty=uep.path[i+1]/W;
		int tx=uep.path[i+1]%W;
		if(cy<ty) S+="D";
		if(cy>ty) S+="U";
		if(cx<tx) S+="R";
		if(cx>tx) S+="L";
	}
	cout<<S<<endl;
	
}

まとめ

オイラー閉路に持ち込むことを忘れていた…。