アプローチは悪くなかったんだけど、詰め切れなかった。
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; } }
まとめ
本番経路は思いついたものの距離の割り当てができなかった。
総当たりしちゃえばよかったのね…。