kmjp's blog

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

TopCoderOpen 2020 Round3A : Medium Hamiltons

アプローチは悪くなかったんだけど、詰め切れなかった。
https://community.topcoder.com/stat?c=problem_statement&pm=15174&rd=18111

問題

6以上の正整数Nと、10以上1000未満の整数Lが与えられる。
N頂点の無向完全グラフを考える。各辺に1~Lの範囲の整数値の距離を設定できるとする。

ここで、最短のハミルトンパスを求める以下の2種のアルゴリズムを考える。

  • 真に最短のハミルトンパスを求める。
  • 真に最短のハミルトン閉路を求め、そこから閉路中の最大距離の辺を1つ取り除く

後者が前者よりL/2以上大きくなるようなグラフを構築せよ。

解法

まず、0-1-2-....-(N-1)-0と閉路を成すように、距離Zの辺を設定したとする。
また、とりあえずそれ以外の辺に距離Lを設定しておく。
後者がこの閉路を選択するようなグラフを構築しよう。すなわち

  • 閉路を作ると距離がNZ以上になる
  • ハミルトンパスを作ると距離が(NZ-L/2)以下になる

を満たしたい。
そこで、「1回は妥協して距離Lの辺をたどることで、ハミルトンパスが距離(NZ-L/2)以下になる」というものを構築しよう。
点0-2を距離X、3-5を距離Yでつないだとする。
これらを両方活用する閉路を考えると距離はX+Y+(N-3)Z+Lになるので、これがN*Zより大きく、かつここからLを取り除いて得られるパスに対し(N-1)*ZがX+Y+(N-3)Z+ceil(L/2)以上であればよい。
(X+Y)とZを総当たりするとO(L^2)で求められる。

以下のコードは検証用の両アルゴリズムを含むため長い。

int dp[1<<14][14];
int dp2[1<<14][14][14][14];
int C[14][14];

class Hamiltons {
	public:
	
	int Maru(int N) {
		int i,mask,j;
		
		FOR(mask,1<<N) FOR(i,N) dp[mask][i]=1<<20;
		FOR(i,N) dp[1<<i][i]=0;
		FOR(mask,1<<N) {
			FOR(i,N) if(mask&(1<<i)) {
				int cur=dp[mask][i];
				FOR(j,N) if((mask&(1<<j))==0) {
					dp[mask|(1<<j)][j]=min(dp[mask|(1<<j)][j],cur+C[i][j]);
				}
			}
		}
		int mi=1<<30;
		FOR(i,N) mi=min(mi,dp[(1<<N)-1][i]);
		//cout<<mi<<endl;
		return mi;
	}
	int Vlado(int N) {
		int i,mask,x,y,j;
		
		FOR(mask,1<<N) FOR(i,N) FOR(x,N) FOR(y,N) dp2[mask][i][x][y]=1<<20;
		FOR(x,N) FOR(y,N) if(x!=y) dp2[(1<<x)|(1<<y)][x][y][y]=C[x][y];
		FOR(mask,1<<N) {
			FOR(x,N) if(mask&(1<<x)) {
				FOR(y,N) if(mask&(1<<y)) {
					FOR(i,N) if(mask&(1<<i)) {
						FOR(j,N) if((mask&(1<<j))==0 && C[i][j]<=C[x][y]) {
							dp2[mask|(1<<j)][x][y][j]=min(dp2[mask|(1<<j)][x][y][j],dp2[mask][x][y][i]+C[i][j]);
						}
					}
				}
			}
		}
		int mi=1<<30,mle=1<<30;
		FOR(x,N) FOR(y,N) FOR(i,N) if(C[x][y]>=C[i][x]) {
			if(dp2[(1<<N)-1][x][y][i]+C[i][x]<mi) {
				mi=dp2[(1<<N)-1][x][y][i]+C[i][x];
				mle=0;
			}
			if(dp2[(1<<N)-1][x][y][i]+C[i][x]==mi) mle=max(mle,C[x][y]);
		}
		//cout<<mi<<" "<<mle<<" "<<mi-mle<<endl;
		return mi-mle;
	}
	
	vector <int> construct(int N, int L) {
		
		int XY,Z;
		int x,y;
		FOR(x,N) FOR(y,N) C[x][y]=L;
		
		for(Z=1;Z<=L;Z++) {
			for(XY=2;XY<=2*L;XY++) {
				if(N*Z<XY+(N-3)*Z+L && (N-1)*Z>=XY+(N-3)*Z+(L+1)/2) {
					FOR(x,N) C[x][(x+1)%N]=C[(x+1)%N][x]=Z;
					C[0][2]=C[2][0]=XY/2;
					C[3][5]=C[5][3]=XY-XY/2;
					goto out;
				}
			}
		}
		out:
		
		assert(Vlado(N)-Maru(N)>=(L+1)/2);
		
		
		vector<int> R;
		FOR(x,N) for(y=x+1;y<N;y++) R.push_back(C[x][y]);
		return R;
	}
}

まとめ

本番経路は思いついたものの距離の割り当てができなかった。
総当たりしちゃえばよかったのね…。