yukicoder : No.95 Alice and Graph

これは解けるべきだった…。
http://yukicoder.me/problems/23

問題

1～N番のN個の頂点と、M本の無向辺からなるグラフが与えられる。
i番目の頂点に初めて通過すると、(2^(i-1)-1)のスコアが得られる。
最大K回まで辺に沿って移動可能とするとき、得られる総最大スコアを求めよ。

解法

1～(i-1)番の頂点をすべてたどるより、i番の頂点を1箇所たどる方が高得点である。
よって辿るべき頂点をbitmaskで管理し、頂点番号の高い順に「この頂点を辿る点に追加してもK回以内の移動で済む」かを判定して、条件を満たせるならその頂点を辿る点に追加する。

「この頂点を辿る点に追加してもK回以内の移動で済む」の判定は、Kが小さいことを利用してBitDPするとO(K^2*2^K)で済む。

得点差が極端で、とにかく高得点な頂点を優先した方がいいっていうの、先日のSRMでも出たね。
TopCoder SRM 632 Div1 Medium CandyCupRunningCompetition - kmjp's blog

int N,M,K;
int mat[100][100];
int dp[1<<17][17];
vector<int> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(x,100) FOR(y,100) mat[x][y]=1000;
	FOR(x,100) mat[x][x]=0;
	FOR(i,M) {
		cin>>x>>y;
		mat[x-1][y-1]=mat[y-1][x-1]=1;
	}
	FOR(i,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
	V.push_back(0);
	
	ll ret=0;
	for(i=N-1;i>0;i--) {
		if(V.size()>=K+1) break;
		
		V.push_back(i);
		memset(dp,0x3f,sizeof(dp));
		dp[1][0]=0;
		for(int mask=1;mask<1<<V.size();mask++) {
			FOR(x,V.size()) if(mask & (1<<x)) {
				FOR(y,V.size()) if(x!=y && (mask & (1<<y))) dp[mask][x] = min(dp[mask][x], dp[mask^(1<<x)][y]+mat[V[x]][V[y]]);
			}
		}
		
		int ok=0;
		FOR(j,V.size()) if(dp[(1<<V.size())-1][j]<=K) ok++;
		if(ok==0) V.pop_back();
		else ret += (1LL<<i)-1;
	}
	
	cout << ret << endl;
}

まとめ

Kが小さいのでBitDPだろうなとは思いつつ、うまくBitDPに落とせず、K手DFSしてTLEしてしまった。