kmjp's blog

競技プログラミング参加記です

CSAcademy Round #81 : E. Fold Polygon

なぜこのシンプルな解法にたどり着かなかったのか。
https://csacademy.com/contest/round-81/task/fold-polygon/

問題

2次元座標における多角形の頂点が与えられる。
この多角形において、隣接する2頂点を選択し、片方を消すという作業を残り1頂点になるまで繰り返すことを考える。
なお、この作業のコストは2頂点間の距離とする。

総コストを最小化するような頂点の選択方法を答えよ。

解法

元の図形について、距離をコストとした完全グラフにおけるMSTを求めよう。
このMSTについてどこか1点を根とすると、葉から順に頂点の削除処理を繰り返していくことで最小コストの畳み込みができる。
削除の順番は残った頂点のうち多角形上で隣接しているものを適宜選んでいけばよい。
MST上で辺が交差することはないので、常にそのような組み合わせは存在する。

なお、この問題はTLが厳しく、MSTを求める段階でクラスカル法を用いるとO(ElogE)かかりちょっと間に合わない。
プリム法でO(V^2)で抑えよう。

int T,N;
ll X[2020],Y[2020];
vector<int> E[2020];
int P[2020];
int C[2020];
int lef[2020],ri[2020];
int vis[2020];
ll D[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		UF<2020> uf;
		cin>>N;
		FOR(i,N) {
			cin>>X[i]>>Y[i];
			C[i]=0;
			lef[i]=(i+N-1)%N;
			ri[i]=(i+1)%N;
			vis[i]=0;
		}
		vis[0]=1;
		FOR(i,N) {
			D[i]=(X[i]-X[0])*(X[i]-X[0])+(Y[i]-Y[0])*(Y[i]-Y[0]);
			P[i]=0;
		}
		FOR(i,N-1) {
			ll be=1LL<<60;
			int tar=0;
			FOR(x,N) if(vis[x]==0) {
				if(D[x]<be) be=D[x],tar=x;
			}
			vis[tar]=1;
			C[P[tar]]++;
			FOR(x,N) if(vis[x]==0) {
				ll nd=(X[x]-X[tar])*(X[x]-X[tar])+(Y[x]-Y[tar])*(Y[x]-Y[tar]);
				if(nd<D[x]) {
					D[x]=nd;
					P[x]=tar;
				}
			}
		}
		
		set<int> cand;
		FOR(i,N) if(C[i]==0) cand.insert(i);
		while(cand.size()) {
			if(cand.size()==1 && *cand.begin()==0) break;
			int cur;
			
			FORR(c,cand) {
				cur=c;
				if(c==0) continue;
				if(P[cur]==lef[cur]||P[cur]==ri[cur]) break;
			}
			cand.erase(cur);
			cout<<cur+1<<" "<<P[cur]+1<<endl;
			ri[lef[cur]]=ri[cur];
			lef[ri[cur]]=lef[cur];
			
			if(--C[P[cur]]==0) cand.insert(P[cur]);
			
		}
		
		
	}
}

まとめ

なぜMSTという発想にいたらなかったのか…。