naoya_t@hatenablog

いわゆるチラシノウラであります

TCO2015 Round2A DIV1 Medium<600> : FoxMeeting

DIV1 Medium Random Challenge第3回

…しようと思ったらTCO R2A前なせいで、TCO (2015|2016) Round (2A|2B|2C) DIV1 しか置いてなかったのでここから。(5/20)

  • 関数内で関数を定義して使えるようになってきた
  • WFで距離を求めるのが当たり前に使えるようになってきた
  • 解けてない(テストケースすら全部通せない) 二分探索で、各狐が(一番遠いところに向かって)距離mだけ動いた時に通るすべての街にマークしていって、マークされた街が全部繋がってるか、みたいな方針を立てた、けどこれは解けてない(たまたまうまくいくケースもあるが)

Editorial見つからない

http://mayokoex.hatenablog.com/entry/2015/06/18/211926

  • (各頂点a)に距離mで近づくことを考える
  • a に1歩2歩3歩…及ばないとき、その空白を誰か他の狐が埋めてくれればいいんだけど;狐vs空白、の二部マッチングとか言うんだけどどゆこと? 全狐について、aから一番遠いやつまでの全範囲を対象に、すべての空白が埋められるか、(ダブリ可で)という。 ダブってもいい二部マッチングってどうやるんだ?

日が空いたけど 5/22 二部マッチング問題だけど 最大移動距離m縛り(二分探索中)で、 1つ1つの都市をゴールに仮定してそこに向かわせてたどり着けた一番近い都市、そこからゴールへの経路上の全都市、を「ゴール集合」として ゴール集合が全部狐でつながれば(埋められれば)いい ・どの狐も、ゴール集合の少なくともどこか1都市にはたどり着ける ・どの都市にも、少なくとも狐1匹がたどり着ければいい 特別なことを考えなくても、最大マッチングでよくて。 あぶれた狐も(他の狐がどこにいようが)その何処かにはたどり着くんだから。 で 狐マッチングの行き先をゴールへの経路上に絞ってると(というか経路上しか見てないと)失敗するケースがある。m以内なら全都市対象にしないとダメ。

で何とか通せたけど、これを本番で通せるってどんだけ?

実装

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#define NDEBUG
// BEGIN CUT HERE
#include "cout11.h"
#undef NDEBUG
// END CUT HERE
#include <cassert>

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)

typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;
typedef pair<int,pair<int,int> > iii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second

class UnionFind {
 public:
  vector<int> data;
 public:
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) { return root(x) == root(y); }
  int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
  int size(int x) { return -data[root(x)]; }
};

int maximum_match_count(vector<pair<int, int> >& possible_pairs) {
    const int infty = 987654321;

    int M = possible_pairs.size();
    if (M <= 1) return M;

    set<int> _part1, _part2;
    for (int i=0; i<M; ++i) {
        int p1 = possible_pairs[i].first, p2 = possible_pairs[i].second;
        _part1.insert(p1);
        _part2.insert(p2);
        // printf(": %d - %d (%d,%d)\n", p1, p2, (p1+p2)/2, (p1-p2)/2);
    }
    vector<int> part1(all(_part1)), part2(all(_part2));
    int P1 = part1.size(), P2 = part2.size();
    map<int, int> part1_map, part2_map;
    for (int i=0; i<P1; ++i) part1_map[part1[i]] = i;
    for (int i=0; i<P2; ++i) part2_map[part2[i]] = i;

    int w = 1 + P1 + P2 + 1;
    // printf("w = 1 + %d + %d + 1 = %d\n", P1, P2, w);

    vector<vector<int> > capacity(w, vector<int>(w, 0));
    for (int i=0; i<P1; ++i) {
        capacity[0][1+i] = 1;
    }
    for (int i=0; i<M; ++i) {
        int p1 = part1_map[possible_pairs[i].first];
        int p2 = part2_map[possible_pairs[i].second];
        assert((0 <= p1 && p1 < P1) && (0 <= p2 && p2 < P2));

        capacity[1+p1][1+P1+p2] = 1;
    }
    for (int i=0; i<P2; ++i) {
        capacity[1+P1+i][1+P1+P2] = 1;
    }
    // cout << capacity << endl;

    // maximum flow
    //int w = capacity.size();
    int s = 0, t = w-1;
    // residual networks
    vector<vector<int> > resid(w, vector<int>(w, 0));
    for (int j=0; j<w-1; ++j) {
        for (int k=j+1; k<w; ++k) {
            resid[j][k] = capacity[j][k]; // = capacity[j][k] - flow[j][k]
            resid[k][j] = 0; // = flow[k][j]
        }
    }
    // find another way
    int total = 0;
    for (total=0; ; ++total) {
        bool another_way = false;
        vector<int> prev(w, infty);
        queue<pair<int, int> > q;
        q.push(pair<int, int>(s, -1));
        while (!q.empty()) {
            pair<int, int> p = q.front();
            int node = p.first, prev_node = p.second;
            q.pop();
            prev[node] = prev_node;
            if (node == t) { another_way = true; break; }
            rep(i, w) {
                if (resid[node][i] == 0) continue;
                if (prev[i] < infty) continue;
                q.push(pair<int, int>(i, node));
            }
        }
        // no more ways
        if (!another_way) {
            return total;
        }
        for (int node=t; node!=s; node=prev[node]) {
            int prev_node = prev[node];
            resid[prev_node][node]--;
            resid[node][prev_node]++;
        }
    }
    return 0;
}

#define INF 99999999
class FoxMeeting {
    public:
    int maxDistance(vector<int> A, vector<int> B, vector<int> L, vector<int> foxes) {
        int n = A.size() + 1;
        assert(1<=n && n<=50);
        assert(sz(A)==n-1 && sz(B)==n-1 && sz(L)==n-1);

        int nFox = sz(foxes);
        assert(1<=nFox && nFox<=n);

        if (nFox == 1) return 0;
        if (nFox == n) return 0; // 鳩ノ巣原理

        for(int& a: A) --a;
        for(int& b: B) --b;
        for(int& f: foxes) --f;

        // 辺いくつで行けるか(実際の距離とは別)
        vector<vector<int>> d1(n, vector<int>(n, INF));
        rep(i, n) d1[i][i] = 0;
        rep(i, n-1) {
            int a = A[i], b = B[i];
            d1[a][b] = d1[b][a] = 1;
        }
        // WF
        rep(i,n) rep(j,n) rep(k,n) {
            d1[j][k] = min(d1[j][k], d1[j][i] + d1[i][k]);
        }

        vector<vector<int>> d(n, vector<int>(n, INF));
        rep(i, n) d[i][i] = 0;
        rep(i, n-1) {
            int a = A[i], b = B[i], l = L[i];
            d[a][b] = d[b][a] = l;
        }
        // WF
        rep(i,n) rep(j,n) rep(k,n) {
            d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
        }

        // 0
        function< bool(vector<int>&) > monolithic = [=](vector<int>& vec) -> bool {
            int N = vec.size();
            UnionFind uf(N);
            repC2(i,j,N) {
                int a = vec[i], b = vec[j];
                if (d1[a][b] <= 1) uf.unionSet(i, j);
            }
            set<int> g;
            rep(i, N) g.insert(uf.root(i));
            return (sz(g) == 1);
        };
        if (monolithic(foxes)) return 0;

        vector<int> farthest_fox(nFox);
        rep(fox1_id, nFox) {
            int fox1_home = foxes[fox1_id];
            int dmax = -1, dmax_at;
            rep(fox2_id, nFox) {
                if (fox2_id == fox1_id) continue;
                int fox2_home = foxes[fox2_id];

                int dij = d1[fox1_home][fox2_home]; // dではなく
                if (dij > dmax) {
                    dmax = dij; dmax_at = fox2_id;
                }
            }
            assert(dmax < 50);
            farthest_fox[fox1_id] = dmax_at;
        }
        // cout << "farthest_fox:" << farthest_fox << endl;

        function< vector<int>(int,int) > get_route = [=](int start_city,int goal_city) {
            vector<int> route;
            if (start_city == goal_city) {
                return vector<int> {start_city};
            }
            set<int> visited;
            for (int here=start_city; ; ) {
                visited.insert(here);
                route.push_back(here);
                if (here == goal_city) break;
                int dh = d[here][goal_city];
                int next_city = here;
                rep(city, n){
                    if (city == here) continue;
                    if (d1[here][city] != 1) continue;
                    if (found(visited, city)) continue;
                    int di = d[city][goal_city];
                    if (di < dh) { next_city = city; break; }
                }
                if (next_city == here) {
                    break;
                }
                here = next_city;
            }
            return route;
        };

        int lo = 0, hi = 100000*n; // p(lo)=false, p(hi)=true;
        while (lo+1 < hi) {
            int m = (lo + hi)/2;

            function< bool(int) > p = [=](int m) -> bool {
                rep(goal, n) {
                    set<int> cloud; // 全員がこのsetのどこかに入る
                    rep(fox_id, nFox) {
                        // いちばん遠いやつをに向かって m だけ動かして
                        int home = foxes[fox_id];
                        vector<int> route = get_route(home, goal);
                        int R = route.size();
                        int last = -1; // mで、route[stopped]まで行ける
                        for (int i=0; i<R; ++i) {
                            int city = route[i];
                            if (d[home][city] <= m) {
                                last = i;
                            } else {
                                break;
                            }
                        }
                        assert(0 <= last && last < R);
                        for (int i=last; i<R; ++i) {
                            int city = route[i];
                            cloud.insert(city);
                        }
                    }
                    assert(found(cloud, goal));
                    if (cloud.size() > nFox) continue; // impossible
                    if (cloud.size() == 1) return true;

                    vector<ii> possible_pairs;
                    tr(it, cloud) {
                        int city_in_cloud = *it;
                        bool visited = false;
                        rep(fox_id, nFox) {
                            int fox_home = foxes[fox_id];
                            if (d[fox_home][city_in_cloud] <= m) {
                                possible_pairs.push_back(ii(city_in_cloud, fox_id));
                                visited = true;
                            }
                        }
                        if (!visited) goto next;
                    }
                    if (maximum_match_count(possible_pairs) == cloud.size()) return true;
                next:
                    ;
                }
                return false;
            };

            bool p_m = p(m);
            if (p_m) {
                hi = m;
            } else {
                lo = m;
            }
        }
        return hi;
    }
};