ICPCアジア地区横浜大会2018 K問題 : Sixth Sense

問題. Sixth Sense

2つの整数列 $p = (p_1, \ldots, p_n), \,\,f = (f_1, \ldots, f_n)$ が与えられる． $i$ 番目の要素が $p_i$ よりも大きくなるような要素が最も多くなるように $f$ を並び替えよ．そのような並び方が複数ある場合は辞書式順序で最も大きいものを求めよ．

制約： $2 \le n \le 5,000$ ，　 $1 \le p_i, \,f_i \le 10,000$

解法

辞書式順序の制約がなければ，二部グラフ $G = (P; F, E)$ の部集合 $P, F$ をそれぞれ列 $p, f$ として，各辺 $\{v_i, v_j\} \in E$ を $p_i < f_j$ として定義したものの上での最大マッチング問題と等しくなります．また， $G$ は Bipartite chain graph なので， $G$ の最大マッチングは $p$ と $f$ をそれぞれ昇順に整列した列 $p', f'$ によって構成される二部グラフ上で， $f'$ を昇順に貪欲的にマッチングすることによって $O(n)$ 時間で求めることができます．
最大マッチングを満たす列の中で辞書式順序で最大のものを見つけることを考えます． $p_i$ に対応する $f$ の要素は二分探索で求めることができます．まだ選ばれていない $f$ の要素を昇順に並べたものを $f'$ として， $p_i$ よりも大きい要素で最も左にあるものを $f'_j$ とします．
まず， $f'$ から $f'_j$ を取り除いた列と $(p_i, p_{i+1}, \ldots, p_n)$ の最大マッチングのサイズを求めます．これが全体の最大マッチングのサイズと等しければ $f'$ から選ばれる要素は $p_i$ よりも大きいことが分かります．したがって， $(f'_j, f'_{j+1}, \ldots, f'_{n})$ が $p_i$ に対応させる候補となります．この候補の列は最大マッチングを保つかどうかで単調性が成立つので，最大マッチングを保つものの中で最大の要素を二分探索で求めることができます．次に，次に， $p_i$ に対応させる候補が $(f'_1, \ldots, f'_{j - 1})$ の場合を考えます．このときも最大マッチングを保つかどうかで単調性が成立つので二分探索で求めることができます．したがって，各 $p_i$ に対して $O(\log n)$ 回の判定で候補となるもを見つけることができ，各判定は $O(n)$ 時間で求めることができるので全体で $O(n^2 \log n)$ 時間で求めることができます．

計算時間： $O(n^2 \log n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int NumWin(const auto &you, const auto &me, size_t pass) {
    int res = 0;
    for (size_t i = 0, j = 0; i < you.size() && j < me.size(); ) {
        if (j != pass && you[i] < me[j]) { ++res; ++i; }
        ++j;
    }
    return res;
}

void Erase(auto &&data, int x) {
    for (size_t i = 0; i + 1 < data.size(); ++i)
        if (data[i] == x) swap(data[i], data[i + 1]);
    data.pop_back();
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> you(n), me(n);
    for (auto &&x : you) cin >> x;
    for (auto &&x : me) cin >> x;

    vector<int> ord(you);
    sort(you.begin(), you.end());
    sort(me.begin(), me.end());

    int max_win = NumWin(you, me, n);

    vector<int> ans; ans.reserve(n);
    for (const int x : ord) {
        Erase(you, x);

        int lb = 0, ub = me.size();
        int idx = distance(me.begin(), lower_bound(me.begin(), me.end(), x + 1));
        if (idx == ub || (x < me[idx]) + NumWin(you, me, idx) != max_win) ub = idx;
        else lb = idx;

        while (1 < ub - lb) {
            int mid = (lb + ub) >> 1;
            if ((x < me[mid]) + NumWin(you, me, mid) == max_win) lb = mid;
            else ub = mid;
        }

        if (x < me[lb]) --max_win;
        ans.push_back(me[lb]);
        Erase(me, ans.back());
    }

    for (int i = 0; i < n; ++i)
        cout << ans[i] << " \n"[i == n - 1];

    return 0;
}