naoya_t@topcoder

SRM430 Div1 Medium: TwinTowns

過去問, 練習 | 18:09 |

とりあえず500点問題をちゃんと解いてみる

あれこれ試行錯誤した末、各都市の姉妹都市提携数（あるいは提携可能な余地）を状態として持つDPで書き直した。

• 全n都市の中から都市を１つ選ぶ
• 残りのn-1都市の中からk個の都市（0≦k≦(maxPartners-その都市が既に提携している都市の数)）を選ぶ各組合せについて、
• 各都市の姉妹都市提携数にこの組合せを加えたものをもとに、
• 都市数が１つ少ない場合について、提携最大数および最短合計距離を算出する。
• 算出結果（提携最大数、最短合計距離）に、この都市からの姉妹提携都市関係を加えて返す。

最初は vector<int> で回していたが、高速化＆メモ化のために long longにパックして回すようにした。

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

inline int get_at(long long arcs, int idx)
{
  return (arcs >> (idx * 2)) & 0x3;
}
inline long long set_at(long long arcs, int idx, int val)
{
  long long mask = 3LL << (idx * 2);
  long long vall = (long long)val << (idx * 2);
  return (arcs & (~mask)) | vall;
}

class TwinTowns {
  int n, maxP;
  int distance[10][10];
  bool available[10][10];

  map<long long,int> memo;

private:
  int findMaximum(long long arcs, int till) {
    if (till == 0) return 0;

    long long key = (arcs << 4) | till;
    if (memo.find(key) != memo.end()) return memo[key];

    int pmax = 0, dmin = INT_MAX;//D_INFTY;
    int count = get_at(arcs,till);

    long long arcs_ = arcs;

    int pat_max = (1 << till) - 1;
    int c_max = maxP - count;

    int arcs_mask = (1 << (till*2)) - 1;

    for (int pat=0; pat<=pat_max; pat++) {
      int c = __builtin_popcount(pat);
      if (c > c_max) continue;

      int d = 0;
      for (int i=0,m=1;i<till;i++,m<<=1) {
        if ((pat & m) == 0) continue;
        if (! available[till][i]) goto next_pat;
        if (get_at(arcs_,i) == maxP) goto next_pat;

        arcs_ = set_at(arcs_, i, get_at(arcs_,i) + 1);
        d += distance[till][i];
      }

      {
        int ans = findMaximum(arcs_ & arcs_mask, till-1);
        int ans_p = c + (ans & 31), ans_d = d + (ans >> 5);
        if (ans_p > pmax) {
          pmax = ans_p; dmin = ans_d;
        } else if (ans_p == pmax) {
          if (ans_d < dmin) dmin = ans_d;
        }
      }
    next_pat:
      arcs_ = arcs;
    }

    int ans = (dmin << 5) | pmax;
    memo[key] = ans;
    return ans;
  }
  
public:
  vector<int> optimalTwinTowns(vector<int> x, vector<int> y, int maxPartners, int minDistance) {
    n = x.size();
    if (n == 1) {
      vector<int> ans(2,0);
      return ans;
    }

    maxP = min(maxPartners,n-1);
    rep(i,n) rep(j,n) available[i][j] = false;

    rep(j,n) {
      rep(i,n) {
        if (i == j) continue;
        int dist = abs(x[i]-x[j]) + abs(y[i]-y[j]); // 1-2000
        if (dist >= minDistance) {
          distance[i][j] = distance[j][i] = dist;
          available[i][j] = available[j][i] = true;
        }
      }
    }

    int a = findMaximum(0, n-1);
    vector<int> ans(2,0);
    ans[0] = a & 31; ans[1] = a >> 5;
    return ans;
  }
};