Maximum-Cup 2013 : A - 特別作戦

あとは本番正答者が多い順に練習。
本番2ケタ人数が解けてる問題はそこまで難しくないね。
http://maximum-cup-2013.contest.atcoder.jp/tasks/maximum_2013_a

問題

N個の町があり、互いの町の間に道を作る場合のコストが与えられる。
N個のどの町が1個破壊されても、残りの(N-1)の町が互いに移動可能なように道を作りたい場合、そのコストを最小化せよ。

解法

N個の町を輪っか状につなげば、どの町が破壊されても残りの町が移動可能。
輪っかの最小コストを求めるには、「今まで到達済みの町」「最後に到達した町」でBitDPしてN*2^Nパターン総当たりすればよい。

なお、N==2の時は例外として1つも道がいらない。

int N,E[20][20];
int dpdp[20][1<<20];

int dfs(int cur,int mask) {
	int i;
	if(dpdp[cur][mask]>=0) return dpdp[cur][mask];
	if(mask==(1<<N)-1) {
		dpdp[cur][mask]=E[cur][0];
	}
	else {
		dpdp[cur][mask]=1<<30;
		FOR(i,N) if((mask & (1<<i))==0) {
			dpdp[cur][mask]=min(dpdp[cur][mask],E[cur][i]+dfs(i,mask | (1<<i)));
		}
	}
	return dpdp[cur][mask];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) for(j=i+1;j<N;j++) {
		cin>>E[i][j];
		E[j][i]=E[i][j];
	}
	if(N==2) return _P("0 0\n");
	MINUS(dpdp);
	_P("%d %d\n",N,dfs(0,1));
}

まとめ

今回のMaximum-Cupはひっかけが多いなぁ。N==2に見事に引っかかった。