TopCoder SRM 809 : Div1 Medium TruckUnion

割と雑な解法取ったら1.94sでギリギリっだった。
(URL未定)

問題

N頂点の完全無向グラフがある。
各頂点間の距離が与えられる。

このグラフに対し、いくつかの閉路を割り当てたい。

• 全閉路0番の頂点のみ共有する
• 各閉路、0番以外の頂点は共有せず、またどの頂点もいずれかの閉路に含まれる。
• 各閉路の頂点数は等しい

各閉路の総和の最小値を求めよ。

解法

閉路の頂点数をdとすると、(N-1)を(d-1)が割り切らないといけない。
そのようなdを総当たりしよう。

2sギリギリで通るテクとしては、まずbitDPである頂点群に対し、閉路長の最小値をO(2^N*N^2)で列挙しておく。
その後、O(3^N)でbitsetのsubsetを列挙するテクで、長さdの閉路に分解していく。
bitset中で、d要素のsubsetを列挙する部分を雑に行うと2sギリギリになった。

dの総当たりは同じように行うとして、もう少し速いテクがある。
閉路長の最小値をO(2^N*N^2)で列挙するbitDPにおいて、0番以外の頂点を(d-1)個たどるたびに一度0番の頂点に戻る、という風にすればよい。
これだと300msぐらいで通った。

以下のコードは、本番後に書き直した後者のもの。

int D[18][18];
int dp[1<<18][18];

class TruckUnion {
	public:

	int optimize(int N, vector <int> C) {
		int y,x;
		FOR(y,N) FOR(x,N) D[y][x]=C[y*N+x];
		int mi=1LL<<30;
		
		int i,j,k,mask;
		for(i=1;i<=N-1;i++) {
			if((N-1)%i) continue;
			
			FOR(mask,1<<N) FOR(j,N) dp[mask][j]=1<<30;
			dp[1][0]=0;
			
			FOR(mask,1<<N) {
				int step=(__builtin_popcount(mask)-1)%i;
				FOR(j,N) if(dp[mask][j]<1<<30) {
					FOR(k,N) if((mask&(1<<k))==0) {
						if(step+1==i) {
							dp[mask|(1<<k)][0]=min(dp[mask|(1<<k)][0],dp[mask][j]+D[j][k]+D[k][0]);
						}
						else {
							dp[mask|(1<<k)][k]=min(dp[mask|(1<<k)][k],dp[mask][j]+D[j][k]);
						}
					}
				}
			}
			mi=min(mi,dp[(1<<N)-1][0]);
		}
		
		return mi;
	}
}

まとめ

本番通ってよかったな…。