RUPC2018 day2 G: Combine Two Elements

解法

１つ目の削除方法が可能なペアに2つ目の削除方法を適用する意味はあるのか考えると、操作回数で得できるわけではなく無駄にペアが多く消えているので得することはなさそう（要証明）。なので、1つ目の削除方法が可能なペアは全てこの方法で削除を行ってよい。
次に2番目の削除方法で最善の消し方を考える。ペアiとjを消せるときiとjの間に辺を張るとする。このとき同じ頂点から生えている辺を複数本選ばないように辺を多く選べばよくこれは最大マッチングとなる。
このままやろうとするとこれは一般マッチングになりそうでやりたくない。ここで a[i]-b[i] の正負に注目する。a[i]-b[i] >= 0 のペア同士を組み合わせても条件を満たすことはありえない。同様にa[i]-b[i] <= 0 のペア同士で条件を満たすことはない。a[i]-b[i]が正の頂点集合とa[i]-b[i]が負の頂点集合に分けることができ、二部グラフとなっている。したがって二部マッチングをすればよい。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

struct b_match {
  static const int MAX_V = 1000;
  int V;
  VI G[MAX_V], match;
  vector<bool> used;

  // V要素で初期化
  b_match(int v_=MAX_V) : V(v_) { match.resize(v_); used.resize(v_); }
  // 辺u-vを追加する
  void add_edge(int u, int v) { G[u].PB(v); G[v].PB(u); }
  // 増加パスの探索
  bool dfs(int v) {
    used[v] = true;
    REP(i, G[v].size()) {
      int u = G[v][i], w = match[u];
      if(w < 0 || !used[w] && dfs(w)) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  // 二部マッチングを計算
  int matching() {
    int res = 0;
    match.assign(V, -1);
    REP(v, V) {
      if(match[v] < 0) {
        used.assign(V, false);
        if(dfs(v)) res++;
      }
    }
    return res;
  }
};

bool use[805];
int x[805], y[805];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, a, b;
  cin >> n >> a >> b;
  REP(i, n) cin >> x[i] >> y[i];

  int ans = 0;
  REP(i, n) {
    if(abs(x[i]-y[i]) <= a || (b <= abs(x[i]-y[i]) && abs(x[i]-y[i]) <= 2*a)) {
      use[i] = true;
      ans++;
    }
  }

  b_match m(n);
  vector<PII> e;
  VI v;
  REP(i, n) FOR(j, i+1, n) {
    if(use[i] || use[j]) continue;
    int diff = abs(x[i]+x[j]-y[i]-y[j]);
    if(diff <= a || (b <= diff && diff <= 2*a)) {
      m.add_edge(i, j);
    }
  }

  cout << ans + m.matching() << endl;

  return 0;
}

ferinの競プロ帳

競プロについてのメモ

RUPC2018 day2 G: Combine Two Elements

解法

ソースコード