cafelier@SRM

Facebook Hacker Cup 2012 R2 Road Removal

FHC, あとで | 21:49 |

今回はUnionFind祭りだった。

• 長いので重要な都市を「黒」と重要でない都市を「白」とする。

struct UnionFind
{
   vector<int> uf, sz;
   int nc;

   UnionFind(int N): uf(N), sz(N,1), nc(N)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   bool Union(int a, int b)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            --nc;
         }
         return (a!=b);
      }
};

typedef int vert;
typedef tuple<vert,vert> edge;

int solve(const vector<edge>& edges, int N, int K)
{
   int removed = 0;

   // とりあえず白白辺を全部結ぶ
   UnionFind uf(N);
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a >= K && b >= K )
         uf.Union(a,b);
   }

   // 他の辺はサイクル作らないように結ぶ
   for(edge e : edges) {
      vert a = get<0>(e);
      vert b = get<1>(e);
      if( a < K || b < K )
         if( !uf.Union(a,b) )
            ++removed;
   }
   return removed;
}

int main()
{
   int T; cin >> T;
   for(int C=1; C<=T; ++C)
   {
      int N, M, K; cin >> N >> M >> K;
      vector<edge> edges;
      for(int i=0; i<M; ++i) {
         int a,b; cin >> a >> b;
         edges.emplace_back(a, b);
      }
      cout << "Case #" << C << ": " << solve(edges, N, K) << endl;
   }
}

• 仮定１： 白白辺はgreedyに全部結んじゃって良い
  • 白白辺 e を含まない最適解が存在したとする
  • その解に e を足すと（最適性より）黒ノードを含むサイクルができる
  • そのサイクル中の白黒辺を消して代わりに e を入れてもサイクルなしなので(※)これも最適解になる
    • ※: eを足した結果できるサイクルは1つだけ。2つ一気にできたとすると絵を描いてみると元々サイクルがあったことになってしまうことがわかる。
• 仮定２： 白白辺で結んだ同値類を１点とみなして、あとは普通に最小全域森を作るのが最適
  • 森なら新しくサイクル作ってないので条件は満たす。
  • それより枝を多く入れると必ずサイクルができてしまう。もう白白辺は存在しないので、この段階でできてしまったサイクルは必ず黒ノードを含むから失格。
  • 故に最小全域森が最適

Facebook Hacker Cup 2012 R2 Monopoly

FHC | 21:50 |

• マージするたびに、「この会社を高さhで作った場合の社長直属の部下の最小数は何人？」という h \mapsto d の表を計算。
• N-1回のマージで、高さは高々（高さは高々！）Nにしかならないので表のサイズはNまでなので、
• O(N^2) 時間あれば終わる。
• この h \mapsto d は単調減少だから確か何か工夫するとオーダー落とせるんだよなあ蟻本蟻本…
• と思っている途中で制約を見たら N≦3万 でした。
• 6分なら9億が20ケースは時間足りますね。
• しかも実際の入力データめちゃくちゃ弱くて一瞬で本当に終わってしまった。

typedef tuple<int, int> merger;

template<typename T>
struct UnionFind
{
   vector<int> uf, sz;
   vector<T> info;
   int nc;

   UnionFind(int N, const T& ini): uf(N), sz(N,1), nc(N), info(N, ini)
      { for(int i=0; i<N; ++i) uf[i] = i; }
   int size()
      { return nc; }
   int Find(int a)
      { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
   T& Info(int a)
      { return info[Find(a)]; }
   template<typename F>
   bool Union(int a, int b, F info_merger)
      {
         a = Find(a);
         b = Find(b);
         if( a != b )
         {
            if( sz[a] >= sz[b] ) swap(a, b);
            uf[a] = b;
            sz[b] += sz[a];
            info_merger(info[b], info[a]);
            --nc;
         }
         return (a!=b);
      }
};

int solve(const vector<merger>& ms, int N, int D)
{
   typedef vector<int> HD;
   static const int INF = 0x3fffffff;

   UnionFind<HD> uf(N, HD({INF,0}));
   for(auto m : ms) {
      uf.Union(get<0>(m), get<1>(m), [&](HD& a, HD b){
         int aMinD = INF;
         int bMinD = INF;
         HD c(max(a.size(),b.size())+1, INF);
         for(int h=1; h<c.size(); ++h) {
            int c1 = aMinD>=INF || h>=b.size() ? INF : b[h]+1;
            int c2 = bMinD>=INF || h>=a.size() ? INF : a[h]+1;
            int c3 = aMinD>=INF || h-1>=b.size() || b[h-1]>=INF ? INF : min(aMinD, b[h-1])+1;
            int c4 = bMinD>=INF || h-1>=a.size() || a[h-1]>=INF ? INF : min(bMinD, a[h-1])+1;
            c[h] = min({c1, c2, c3, c4, INF});
            if(c[h]>D) c[h] = INF;
            if(h<a.size()) aMinD = min(aMinD, a[h]);
            if(h<b.size()) bMinD = min(bMinD, b[h]);
         }
         a = c;
      });
   }
   HD& hd = uf.Info(0);
   for(int h=0; h<hd.size(); ++h)
      if( hd[h] <= D )
         return h;
   return -1;
}

int main()
{
   int T; cin >> T;
   for(int C=1; C<=T; ++C)
   {
      int N, D; cin >> N >> D;
      vector<merger> ms(N-1);
      for(auto& m : ms) {
         cin >> get<0>(m) >> get<1>(m);
         -- get<0>(m);
         -- get<1>(m);
      }
      cout << "Case #" << C << ": " << solve(ms, N, D) << endl;
   }
}