競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 178F問題

ABC178F

より簡単な類題

「Size が \(2N\) の multiset \(c\) が与えられる． この中からペアを \(N\) 個作る． ただし，異なる元同士をペアにしなければならない．」 という問題を考える． これが可能である必要十分条件は，

\(c\) における一番多い元 \(x\) の個数 \(cx\) が \(\frac{\#c}{2}\) 個以下であること．\(\cdots [P(c)]\)

必要性は，もしある元 \(x\) の個数が \(N\) 個より多ければ， \(x\) 同士でペアにしないといけないので不可能，ということから分かる． 十分性は， 一番多い元 \(x\) と，\(y \in c\) \*1{

      // *it_m = [elm, cnt]
      assert*2;
      assert(it_p != p.end());

      // update
      {
        cnt += d; assert(cnt >= M(0));
        p.erase(it_p);
       
        (*it_m).second = cnt;
        p.insert(make_pair(cnt, elm));
      }
    }else{
      mlty.insert(make_pair(elm,M(d))); // mlty[elm] = d;
      p.insert(make_pair(M(d),elm));
    }

    sz += d;
    assert(mlty.find(elm) != mlty.end() && mlty[elm] >= M(0));
    assert(sz >= M(0));
  }

  void insert(T elm, M d = 1){
    add(elm, d);
  }

  void remove(T elm, M d = 1){
    add(elm, -d);
   
    if(mlty.find(elm) != mlty.end() && mlty[elm] == M(0)) {
      mlty.erase(elm);
      p.erase(make_pair(M(0), elm));
    }

  }

  bool in(T elm){
    if(mlty.find(elm) != mlty.end() && mlty[elm] >= M(0)){
      return true;
    }else return false;
  }

  M size(){
    return sz;
  }

 
};

int main() {
  ll n;
  cin >> n;
  multiset<ll> a,b;
  MS<ll> ab;
  rep(i,n){
    ll x; cin >> x;
    --x;
    a.insert(x);
    ab.insert(x);
  }
  rep(i,n){
    ll x; cin >> x;
    --x;
    b.insert(x);
    ab.insert(x);
  }

  for(auto [_, cnt]: ab.mlty){
    if(cnt > n) {
      cout << "No" << endl;
      return 0;
    }
  }

  vector<pll> ans;
  while(ab.size()){
    auto [cx,x] = *prev(ab.p.end());// cxは使わない

    auto f = [&](multiset<ll> &a, multiset<ll> &b) -> ll {
      ll y = -1;
      if(*b.begin() != x) y = *b.begin();
      if(*prev(b.end()) != x) y = *prev(b.end());
      assert(y != -1);

      a.erase(a.find(x));
      b.erase(b.find(y));

      ab.remove(x);
      ab.remove(y);

      return y;
    };
   
    ll y;
    if(a.find(x) != a.end()){
      y = f(a,b);
      ans.push_back({x,y});
    }else if(b.find(x) != b.end()){
      y = f(b,a);
      ans.push_back({y,x});
    }else assert(false);
  }

  sort(all(ans));
  cout << "Yes" << endl;
  for(auto [_,y]: ans){
    cout << y+1 << " ";
  }

  return 0;
}

*1:y \neq x)\) をペアにしていけば， \(c' = c - \{\ x,y\ \}\) もまた \(P(c')\) を満たすため． 注意として， \(cx = N\) となる異なる\(x\) は，高々 2つになる．

解法

本問も同様に解ける． Multiset \(a,b\) の union \(c\) を考える． \(c\) において一番多い元の個数が \(N\) を超える場合は不可能． 逆に，\(N\) 個以下の場合は可能．
\(c\) において一番多い元を \(x\) とおく． \(x\) の個数が \(Size(a)\) 以下であると仮定する． 帰納法で，ペアのリストが作れることを示す．
\( Size(a) = Size(b) = 1\) のときは明らか． \( Size(a) = Size(b) > 1\) とする． \(x \in a\) のとき， 仮定から，ある \(y \in b\) が存在して \(x \neq y\). よって， \(a\) から \(x\) を取り除き， \(b\) から \(y\) を取り除き， \(c = a \cup b\) で取り直す． 新しい \(a,b,c\) に対しても， \(x\) の個数が \(Size(a)\) 以下となる． \(x \in b\) の場合も同様．

実装

Multiset のクラスを独自に作った． \(c\) から一番多い元をとってくるときと， \(c\) から削除する操作をしたいため．
mlty : 元 -> multiplicity だけでなく， p : multiplicity -> 元 を用意することで実装した．

注意

c++ の multiset は，erase するときに iterator を指定しないと， 指定した元が全て消えてしまう．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

template<typename T>
struct MS{
  using M = long long; // multiplicity
  M sz; // the size of this multiset
public:
  // <cnt> is the multiplicity of <elm>
  map<T,M> mlty; // mlty[elm] = cnt
  set<pair<M,T>> p; // {cnt, elm} in p

  MS(){
    sz = M(0);
  }

  void add(T elm, M d){
    auto it_m = mlty.find(elm);
    if(it_m != mlty.end(

*2:*it_m).first == elm);

      M cnt = (*it_m).second;

      auto it_p = p.find(make_pair(cnt, elm