TopCoder SRM 851 : Div1 Easy Div2 Hard BusTravel

普段と違う環境だしなんかアリーナ重かった。
https://community.topcoder.com/stat?c=problem_statement&pm=18146

問題

N個の町があり、そのうちS個の町を選んでコンテストを開く。
各町から人が集まれるよう、追加で(N-S)個、2つの町の間に片道のバスを運行させることを考える。

各バスは順番に運行するものとする。
各町の間を走るバスの運行コストが与えられるとき、コンテストを開く町とバスの運行箇所を適切に選び、総コストの最小値を求めよ。

解法

バスはN-S個しか運用できないので、N頂点のグラフに対しバス路線を辺で表すと、S要素の連結成分からなる森を作ることになる。
また、バスが走る場合は出発点の町にいる人は必ずそれにのって移動しなければならない。

そこで、単純にBitDPの要領でまだ人のいる可能性がある町を状態とし、バスの運行パターンを総当たりしよう。
最終的に人がいる町がS個になるまでそれを続ければよい。

int C[26][26][26];
ll dp[1<<16];
class BusTravel {
	public:
	int optimize(int N, int S, int M, int A) {
		int x,y,z;
		FOR(x,N) FOR(y,N) FOR(z,N) C[x][y][z]=1LL*(x+1)*(y+4)*(y+z+A)%M+1;
		int mask;
		FOR(mask,1<<N) dp[mask]=1LL<<60;
		dp[(1<<N)-1]=0;
		ll mi=1LL<<60;
		for(mask=(1<<N)-1;mask>=0;mask--) {
			int b=__builtin_popcount(mask);
			if(b<=S) {
				mi=min(mi,dp[mask]);
			}
			else {
				int bid=N-b;
				FOR(x,N) if(mask&(1<<x)) {
					FOR(y,N) if((mask&(1<<y))&&x!=y) {
						dp[mask^(1<<x)]=min(dp[mask^(1<<x)],dp[mask]+C[bid][x][y]);
					}
				}
			}
		}
		return mi;
	}
}

まとめ

Easyとはいえ、ひねりのない問題だったな…。