Single Round Match 430 (Div1/500point)

都市の座標と条件が与えられ、条件を満たすなるべく多いペア(2つの都市の「姉妹都市」関係)を作れ、という典型的なグラフ問題。条件とは「都市がminDistance以上離れている」と「一つの都市は最大maxPartner個の都市と姉妹都市になれる」の2つ。「ペアの個数が最大になるいくつかのペアの作り方のうち、一番距離の合計が短いものを選べ」という条件もついている。

都市の数は最大10個、maxPartnerは最大で3なので、ペアになりうる組み合わせは最大45個、ペアの個数の最大は15個。全探索しても枝刈りをうまくやれば大丈夫じゃないかな、と思って試してみた。

class TwinTowns {
public:
  int MAX_EDGES;
  size_t N;
  vector<pair<int, int> > edges;
  vector<int> edgesLen;
  size_t NUM_EDGES;
  int MAX_PARTNERS;
  int resultDist;
  int resultEdges;

  void recur(size_t i, int numEdges, int dist, vector<int>& degree){
    int v0 = edges[i].first;
    int v1 = edges[i].second;
    if(degree[v0] == MAX_PARTNERS || degree[v1] == MAX_PARTNERS){
      // can't add the edge
      return;
    }
    numEdges++;
    dist += edgesLen[i];
    if(dist > resultDist && numEdges <= resultEdges){
      // too distant
      return;
    }
    if(numEdges > resultEdges){
      resultEdges = numEdges;
      resultDist = dist;
    }else if(numEdges == resultEdges && dist < resultDist){
      resultDist = dist;
    }
    if(numEdges < MAX_EDGES){
      degree[v0]++;
      degree[v1]++;
      // enough room to add edge
      for(size_t j=i+1; j<NUM_EDGES; j++){
	recur(j, numEdges, dist, degree);
      }
      degree[v0]--;
      degree[v1]--;
    }
  }
  vector <int> optimalTwinTowns(vector <int> x, vector <int> y, int maxPartners, int minDistance) {
    N = x.size();
    MAX_PARTNERS = maxPartners; 
    edges.clear();
    edgesLen.clear();

    for(size_t i=0; i<N; i++){
      for(size_t j=i+1; j<N; j++){
        int len = abs(x[i] - x[j]) + abs(y[i] - y[j]);
	if(len >= minDistance){
	  edges.push_back(make_pair(i, j));
	  edgesLen.push_back(len);
	}
      }
    }
    NUM_EDGES = edges.size();
    vector<int> degree(N);
    MAX_EDGES = N * maxPartners / 2;
    resultEdges = 0;
    resultDist = 2000 * 100; // infinity
    vector<int> result;
    for(size_t i=0; i<NUM_EDGES; i++){
      recur(i, 0, 0, degree);
    }
    result.push_back(resultEdges);
    result.push_back(resultDist);
    return result;
  }
}

システムテストに十分短い時間で通ったのでsubmitしたのだけど

    if(dist > resultDist && numEdges <= resultEdges){
      // too distant
      return;
    }

ダメダメですな。まだ正解の見つかっていない状態ではresultEdgesは正解より小さい値になっている可能性があるからこれでは枝を刈りすぎている。かといってこれをコメントアウトすると普通にタイムアウトになる。さて、どうするのが正解か。。

位数とその位数のときの今までで一番短かったのとを記録しておいて、それで枝刈りをするようにした。

class TwinTowns {
public:
  size_t N;
  vector<pair<int, int> > edges;
  vector<int> edgesLen;
  size_t NUM_EDGES;
  int MAX_PARTNERS;
  int resultDist;
  int resultEdges;
  vector<int> cache;

  int getDegree(int deg, int i){
    return (deg >> (i * 2)) & 3;
  }
  int setDegree(int deg, int i, int v){
    return (deg & ~(3 << (i * 2))) | (v << (i * 2));
  }

  void recur(size_t i, int numEdges, int dist, int degree){
    int v0 = edges[i].first;
    int v1 = edges[i].second;
    if(getDegree(degree, v0) == MAX_PARTNERS || getDegree(degree, v1) == MAX_PARTNERS){
      // can't add the edge
      return;
    }
    numEdges++;
    dist += edgesLen[i];
    if(numEdges > resultEdges){
      resultEdges = numEdges;
      resultDist = dist;
    }else if(numEdges == resultEdges && dist < resultDist){
      resultDist = dist;
    }

    degree = setDegree(degree, v0, getDegree(degree, v0) + 1);
    degree = setDegree(degree, v1, getDegree(degree, v1) + 1);
    if(cache[degree] == 0 || dist <= cache[degree]){
      // add edge
      cache[degree] = dist;
      for(size_t j=i+1; j<NUM_EDGES; j++){
	recur(j, numEdges, dist, degree);
      }
    }

  }
  vector <int> optimalTwinTowns(vector <int> x, vector <int> y, int maxPartners, int minDistance) {
    N = x.size();
    MAX_PARTNERS = maxPartners; 
    edges.clear();
    edgesLen.clear();
    cache.clear();
    cache.resize(1 << (2 * N));
    for(size_t i=0; i<N; i++){
      for(size_t j=i+1; j<N; j++){
        int len = abs(x[i] - x[j]) + abs(y[i] - y[j]);
	if(len >= minDistance){
	  edges.push_back(make_pair(i, j));
	  edgesLen.push_back(len);
	}
      }
    }
    NUM_EDGES = edges.size();
    resultEdges = 0;
    resultDist = 0;
    for(size_t i=0; i<NUM_EDGES; i++){
      recur(i, 0, 0, 0);
    }
    vector<int> result;
    result.push_back(resultEdges);
    result.push_back(resultDist);
    return result;
  }
}

結果

Args:
{{851, 33, 108, 369, 127, 778, 434, 88, 873, 246}, {646, 532, 395, 134, 364, 276, 72, 592, 628, 249}, 3, 649}

Expected:
{14, 12205}

Received:
{14, 12325}

うーん。