これは解けるべきだった…。
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してしまった。