B. Swaps (Codeforces Round #743 (Div. 2))

問題

https://codeforces.com/contest/1573/problem/B

問題概要

長さnの2つの数列aとbが与えられる。aは2n以下のそれぞれ異なる奇数が、bは2n以下のそれぞれ異なる偶数が任意の順に格納されている。

これらの数列に対して以下の操作を行うことができる。

• aまたはbのいずれかの数列を選び
• 選んだ数列の任意の隣接する2項を入れ替える

上記の操作を行って、辞書順でaをbより小さくしたい。必要な操作の最小数を答えよ。

考察

aには奇数のみ、bには偶数のみが格納されているので、aの要素とbの要素が一致することはありません。したがって辞書順でaがbより小さくなる必要十分条件はa[0] < b[0]となります。

操作数を少なくしたいため、条件を満たす数はできるだけ数列の前の方から取ってくる必要がありますが、愚直に探索するとO(N²)かかってしまうため間に合いません。

ここで、bについて累積maxをとると、任意のaの要素に対して最も手前にあるbの要素の存在する位置を二分探索で求めることが可能となります。なので、aを全探索しても計算量はO(NlogN)となり、無事答えを出すことができます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<int> b(n);
        vector<int> mx(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            if (i == 0) mx[0] = b[0];
            else mx[i] = max(mx[i - 1], b[i]);
        }

        int ans = 100100;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(mx.begin(), mx.end(), a[i]);
            ans = min(ans, i + (int)distance(mx.begin(), it));
        }
        cout << ans << endl;
    }
}

反省

コンテスト中に通せず、翌日しばらく考えてもわからず、Twitterで解法を漁ってようやく通せました。言われてみればなるほどなんですが・・・。

いやでもこれ1000の難易度ではなくないか？と思ったら案の定*1400のタグがついてましたね。