「辞書順最大」という条件さえなければ典型的な Greedy マッチングではあるね。「辞書順最大」になっても頑張れば基本に忠実にできる。ややこしいけど頑張ればできる感じかな。。。

問題概要

$N$ 人対 $N$ 人の対戦割当を決めたい。敵が 1 回戦、2 回戦、...、 $N$ 回戦で誰が出て来るのかは予め全部わかっているとする。 $i$ 回戦目に出て来る敵の強さは $p_i$ で与えられる。

こちらの $N$ 人の強さは $f_1, f_2, \dots, f_N$ で与えられる。

$N$ 回戦のうち、こちらの強さが相手の強さを上回る回数が最大となるようにしたい。そのような $f_1, f_2, \dots, f_N$ の並び替えのうち、辞書順が最大のものを求めよ。

制約

$1 \le N \le 5000$

考えたこと

もし「辞書順最大」という条件がなかったら

$p$ を小さい順にソート
$f$ を小さい順にソート

してあげて、 $p$ を小さい順に見て、それに勝てる $f$ のうち一番小さいやつをぶつけるようにして行けばいい。こんな感じ (jibun と aite がソート済み)

int max_matching(const deque<int> &aite, const deque<int> &jibun) {
    int i = 0, j = 0;
    for (; i < aite.size() && j < jibun.size(); ) {
        if (aite[i] < jibun[j]) ++i, ++j;
        else ++j;
    }
    return i;
}

辞書順最大にするためには

i 回戦目で残っている jibun のメンバーのうち、aite[i] にぶつけたとして、残りを最適化すれば最大マッチングを達成できるような最大のメンバー

を Greedy に選んでいけばいい。そのようなメンバーの選び方はちょっと場合分けする。

aite[i] に勝つようにぶつけて OK のとき

この判定は、aite[i] より大きい最小の jibun メンバーをぶつけてみて、残りで最大マッチングを組んだときに最大を達成できるかどうかを判定すればいい。

それが Yes だったときは aite[i] に勝てるメンバーのみを考えればいいが、そのとき

aite[i] にぶつける jibun メンバーが大きくなるほど、残るメンバーが弱くなるので厳しくなる

という状況にある。このギリギリのところを二分探索によって求めることができる。

aite[i] に勝つようにぶつけると NG のとき

aite[i] には負けることを選択すべきな場合、やはり

aite[i] にぶつける jibun メンバーが大きくなるほど、残るメンバーが弱くなるので厳しくなる

という状況になるので、このギリギリのところを二分探索によって求めることができる。

まとめると

まとめると、 $N$ 回のステップをそれぞれ二分探索で処理できて、二分探索の各ステップは $O(N)$ で判定できる。

よって全体として計算量は $O(N^{2} \log{N})$ になる。

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

int max_matching(const deque<int> &aite, const deque<int> &jibun) {
    int i = 0, j = 0;
    for (; i < aite.size() && j < jibun.size(); ) {
        if (aite[i] < jibun[j]) ++i, ++j;
        else ++j;
    }
    return i;
}

int main() {
    int N; cin >> N;
    deque<int> aite(N), jibun(N);
    for (int i = 0; i < N; ++i) cin >> aite[i];
    for (int i = 0; i < N; ++i) cin >> jibun[i];
    deque<int> sortaite = aite;
    sort(sortaite.begin(), sortaite.end());
    sort(jibun.begin(), jibun.end());
    
    int mm = max_matching(sortaite, jibun);
    deque<int> res;
    for (int i = 0; i < N; ++i) {
        deque<int> sortaite_next;
        bool finish = false;
        for (int j = 0; j < sortaite.size(); ++j) {
            if (sortaite[j] == aite[0] && !finish) {
                finish = true;
                continue;
            }
            sortaite_next.push_back(sortaite[j]);
        }

        // check can win
        int first = (int)jibun.size();
        for (int j = 0; j < jibun.size(); ++j) {
            if (jibun[j] > aite[0]) {
                first = j;
                break;
            }
        }
        deque<int> temp_jibun;
        for (int j = 0; j < jibun.size(); ++j) {
            if (j == first) continue;
            temp_jibun.push_back(jibun[j]);
        }
        int tmm = max_matching(sortaite_next, temp_jibun) + 1;
        
        // binary search (low: ok id, high: ng id)
        int low, high;
        if (tmm == mm) low = first, high = (int)jibun.size();
        else low = 0, high = first;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            int val = jibun[mid];
            
            temp_jibun.clear();
            for (int j = 0; j < jibun.size(); ++j) {
                if (j == mid) continue;
                temp_jibun.push_back(jibun[j]);
            }
            tmm = max_matching(sortaite_next, temp_jibun);
            if (val > aite[0]) ++tmm;
            if (tmm < mm) high = mid;
            else low = mid;
        }
        
        // match i-th player
        if (jibun[low] > aite[0]) --mm;
        res.push_back(jibun[low]);
        jibun.erase(jibun.begin() + low);
        aite.pop_front();
        sortaite = sortaite_next;
        
        if (mm == 0) break;
    }
    sort(jibun.begin(), jibun.end(), greater<int>());
    for (auto val : jibun) res.push_back(val);
    
    for (int i = 0; i < res.size(); ++i) {
        cout << res[i];
        if (i != (int)res.size() - 1) cout << " ";
    }
    cout << endl;
}