天下一プログラマーコンテスト2013 予選B : E - 天下一最短路コンテスト

さてE。実質これ解いた人がTシャツ圏内だった問題。
http://tenka1-2013-qualb.contest.atcoder.jp/tasks/tenka1_2013_qualB_e

問題

1～Nまでidが振られたN個の格子点をすべて辿る最短経路問題を考える。
タクヤ君のアルゴリズムは、最寄りの点を順にたどる。
高橋君のアルゴリズムは、最後の２点を除き、２番目に最寄の点を順にたどり、最後の２点だけは最寄りの点を辿る。
両者とも、同じ距離の点が複数ある場合、IDが近い方を距離が近いと判定する。

高橋君の方が総距離が短くなる点配置を返せ。

解法

想定解法はランダム配置などを使った探索だが、題意を満たす配置を直接作ることもできる。

自分が本番中考えたのは、問題文にあるIDに関する条件。
これを用いて、同じ距離に複数点がある場合、タクヤ君は後々不利になるような方向に誘導するようIDを振ればいいのでは…と考えた。
ただこれが難しく、10x10のタイル状に点を並べて渦巻きにしたりダイヤ型配置もうまくいかなかった。

結局時間内に解けなかったので周りの回答を参考にした。
2x50の形状に点を配置して、うまくIDを振ればよい。
例えば以下の順。

• (0,0)～(0,48)
• (1,0)～(1,48)
• (0,49)
• (1,49)

タクヤ君のは上記配列では(0,0)→(0,48)→(1,48)→(1,0)→(1,49)→(0,49)と、(0,49)(1,49)を後回しにするために総距離が147と長くなる。
高橋君は(0,0)(1,0)(0,1)(1,1)…とジグザグに移動するが、最後に後回しにする箇所が無いので、118.88程度でだいぶ短くなる。

せっかくなので検証プログラムを載せておく。

void test(vector<pair<ll, ll> >& V) {
	int N=V.size();
	int i,j,k,cur,tar;
	int vis[100];
	double d;
	vector<int> P;
	
	// 1st
	ZERO(vis);
	tar=0;
	d=0;
	vis[0]=1;
	P.push_back(0);
	FOR(i,N-1) {
		vector<ll> C;
		cur=tar;
		FOR(j,N) {
			if(vis[j]) continue;
			C.push_back(((V[cur].first-V[j].first)*(V[cur].first-V[j].first)
				+(V[cur].second-V[j].second)*(V[cur].second-V[j].second))*100+j);
		}
		sort(C.begin(),C.end());
		tar=C[0]%100;
		d += sqrt(C[0]/100);
		P.push_back(tar);
		vis[tar]=1;
	}
	_P("%12lf (",d);
	FOR(i,N) _P("%d ",P[i]+1);
	_P(")\n");
	
	// 2st
	ZERO(vis);
	tar=0;
	d=0;
	vis[0]=1;
	P.clear();
	P.push_back(0);
	FOR(i,N-1) {
		vector<ll> C;
		cur=tar;
		FOR(j,N) {
			if(vis[j]) continue;
			C.push_back(((V[cur].first-V[j].first)*(V[cur].first-V[j].first)
				+(V[cur].second-V[j].second)*(V[cur].second-V[j].second))*100+j);
		}
		sort(C.begin(),C.end());
		if(C.size()>2) {
			tar=C[1]%100;
			d += sqrt(C[1]/100);
		}
		else {
			tar=C[0]%100;
			d += sqrt(C[0]/100);
		}
		
		P.push_back(tar);
		vis[tar]=1;
	}
	_P("%12lf (",d);
	FOR(i,N) _P("%d ",P[i]+1);
	_P(")\n");
	
}

void solve() {
	int f,r,i,j,k,l,x,y,tx,ty,aa[5];
	cin>>j;
	
	vector<pair<ll, ll> > V;
	FOR(i,j) {
		cin>>x>>y;
		V.push_back(make_pair(x,y));
	}
	
	test(V);
	
	return;
}

まとめ

やっぱりちょっと配点高すぎな気が…。