Member SRM 468 Div2 Hard Gifts

問題

グリッド状の迷路が与えられる。各グリッドはいくつかのタイプが有り、各タイプは以下のようになっている。

'.'　通過できる
'#'　壁。通過できない
'K'　スタート地点
'Q'　ゴール地点
'G' 宝物

スタートから初めて宝物をなるべく多く集めながらゴールにたどり着きたい。C個の宝物を持っている時に1つグリッドを動くには(C + 1)の時間が必要になる。また宝物のあるグリッドにたどり着いてもその宝物を拾わなくてもよい。またゴール地点を一度通過して、また戻ってくることも可能である。

T時間でゴールに移動できる手順の内、手に入る宝物の最大値を返せ。

やりかた

bitDP。
dp[S][i] := （Sの集合の宝物を集め、現在宝物iのあるグリッドにいるためのスタートからの最短時間）とすると

という更新式になる。最終的に各状態からゴールに至った場合の最終的なかかる時間を計算し、それが時間Tより小さい場合にはその状態での宝物の数を記録していく。この記録値の最大値がこたえになる。

大変めんどうだけれど宝物、スタート、ゴール間のすべてのペアについて予め、距離を計算しておく必要がある。実装にさく労力のほとんどはここ。もしかするとまた使うのでライブラリみたいにしてしまってもいいかもしれない。

以下とてもきたないソース。

static const ll INF = (1LL << 50);

ll d[20][20];
ll dist[60][60];
ll dp[1 << 17][20];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int N, M;

class Gifts {
public:
  bool inside(int y, int x){return 0 <= y && y < N && 0 <= x && x < M;}
  int maxGifts(vector <string> city, int T) {
    int result = 0;
    vector<int> p;
    map<int, int> num;
    int cnt = 0;
    int sx, sy, gx, gy;
    N = city.size(); M = city[0].length();
    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++){
	if(city[i][j] == 'G'){
	  num[j + i * M] = cnt++;
	  p.push_back(j + i * city[0].length());
	}else if(city[i][j] == 'K'){
	  sy = i; sx = j;
	}else if(city[i][j] == 'Q'){
	  gy = i; gx = j;
	}
      }
    p.push_back(sx + sy * M); num[sx + sy * M] = cnt;
    p.push_back(gx + gy * M); num[gx + gy * M] = cnt + 1;
    for(int k = 0; k < (int)p.size(); k++){
      for(int i = 0; i < 60; i++) fill(dist[i], dist[i] + 60, INF);
      queue<int> Q;
      Q.push(p[k]);
      dist[p[k] / M][p[k] % M] = 0;
      while(!Q.empty()){
	int y = Q.front() / M;
	int x = Q.front() % M;
	Q.pop();
	for(int i = 0; i < 4; i++){
	  int ny = y + dy[i];
	  int nx = x + dx[i];
	  if(inside(ny, nx) && city[ny][nx] != '#' && dist[ny][nx] == INF){
	    Q.push(ny * M + nx);
	    dist[ny][nx] = dist[y][x] + 1;
	  }
	}
      }
      for(int i = 0; i < (int)city.size(); i++)
	for(int j = 0; j < (int)city[0].length(); j++)
	  if(isalpha(city[i][j])){
	    d[k][num[i * M + j]] = dist[i][j]; 
	    d[num[i * M + j]][k] = dist[i][j]; 
	  }
    }
    int C = p.size() - 2; 

    for(int S = 0; S < 1 << 17; S++)
      for(int i = 0; i < 20; i++)
	dp[S][i] = INF;

    for(int i = 0; i < N; i++)
      for(int j = 0; j < M; j++)
	if(city[i][j] == 'G')
	  dp[1 << num[i * M + j]][num[i * M + j]] = d[num[sx + sy * M]][num[i * M + j]];
   
    for(int S = 0; S < 1 << C; S++){
      for(int i = 0; i < C; i++){
	for(int j = 0; j < C; j++){
	  if(!(S >> i & 1)){
	    int c = __builtin_popcount(S);
	    dp[S | 1 << i][i] = min(dp[S | 1 << i][i], dp[S][j] + (c + 1) * d[i][j]);
	  }
	}
      }
    }
    for(int S = 0; S < 1 << C; S++) {
      for(int i = 0; i < C; i++){
	if(S >> i & 1){
	  int c = __builtin_popcount(S);
	  if(dp[S][i] + (c + 1) * d[i][C + 1] <= T) result = max(result, c);
	}
      }
    }
    return result;
  }
};

INFの値を少し小さくしており、それが原因でwaだった。直したら一発ac。
あとちょっと。