ARC111-C Too Heavy

まあ言われりゃ簡単なんだよねこういうのも... あんまコンテスト中考えてなかったけどTwitterとかで大体見ちゃったのでとりあえず通した。

問題概要

https://atcoder.jp/contests/arc111/tasks/arc111_c

N人の人とN人の荷物がある。体重A_iの人 i は、重さB_p[i] の荷物p[i] を持っている。 人 i と人 j の持っている荷物を交換する、という操作を繰り返すことによって、全ての人 i が、荷物 i を持っている、という状態にしたい。ただし、人 i は体重 A_i 以上の重さの荷物を持った時点で、それ以上荷物交換の操作に加わることはできない。最小の操作回数でこれを実現する操作列を構築せよ。また、どのように操作しても実現できない場合は-1を出力せよ。

• 1 ≤ N ≤ 200000

解法

• 自明な不可能条件( B[i] >= A[i] && i != p[i] )は先に弾いておく。

• 置換を巡回置換に分割すると、巡回置換の中で体重が軽い人から順番に荷物を渡していくことが最適。人 i に荷物 i を渡すためのswap操作は下の絵のように、サイクルのサイズを1小さくすることに対応しており、これを繰り返すことが操作回数最小を満足することは明らか。

下の実装では p[i] = x が人 i が荷物 x を持っている、ということに対応し、owner[x] = i が荷物 x は人 i によって所有されている、ということに対応している。swap操作によってこの接続の繋ぎかえのようなことを行なっている。

#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n;cin >> n;
    vector<int> a(n),b(n),p(n),owner(n);
    
    for(int i=0;i<n;i++)cin >> a[i];
    for(int i=0;i<n;i++)cin >> b[i];
    for(int i=0;i<n;i++)cin >> p[i] , p[i]-- , owner[p[i]] = i;
    
    for(int i=0;i<n;i++){
        if(b[p[i]]>=a[i] && i != p[i]){
            cout<<-1<<'\n';
            return 0;
        }
    }
    
    vector<int> idx(n,0);iota(idx.begin(),idx.end(),0);
    sort(idx.begin(),idx.end(),[&](int& i,int& j){
        return a[i] < a[j];
    });
    
    vector<pair<int,int>> ans;
    for(int i : idx){
        if(i != p[i]){
            int j = owner[i];
            ans.emplace_back(i+1,j+1);
            owner[p[i]]=j;
            p[j]=p[i];
            owner[i]=i;
        }
    }
    
    cout<<ans.size()<<'\n';
    for(auto[a,b]:ans){
        cout << a << ' ' << b << '\n';
    }
}