yukicoder : No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ

これはすんなりだった。
https://yukicoder.me/problems/no/2652

問題

L*Lのグリッド上にN個の点が指定される。
ドローンが閉路描くように移動するが、その際の距離はマンハッタン距離で計算される。
N個の点を通るような閉路を構築せよ。ただしその距離は1000L以下とすること。

解法

Mo's Algorithmの要領で、グリッドを√Lの行ごとに分け、行ごとに左から右、右から左と操作しながら行内の点を通過すればよい。

int T,N,L;
int X[202020],Y[202020];
const int DI=300;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>L;
		vector<vector<int>> V;
		
		int span=L/DI+1;
		FOR(i,N) {
			cin>>x>>y;
			if(y/span%2==0) V.push_back({y/span,x,y});
			else V.push_back({y/span,-x,y});
		}
		sort(ALL(V));
		cout<<N<<endl;
		FORR(v,V) {
			if(v[0]%2) v[1]=-v[1];
			cout<<v[1]<<" "<<v[2]<<endl;
		}
		
	}
}

まとめ

昔のARCで、閉路じゃなく全域木でこれをやる感じの問題あったよね。