第2回全国統一プログラミング王決定戦予選 C - Swaps

問題

任意の置換は巡回置換の積に分解できる。また、n要素の巡回置換は、n-1個の互換の積に分解できる。したがって、ある置換がn-2個の互換で表せる⇔2つ以上の巡回置換の積に分解できる。

ここで、\{A_{i}\}を昇順にソートするような置換pを考える。pが2個以上の巡回置換の積に分解できるなら明らかにYES。

pが2個以上の巡回置換に分解できないならば、pはn要素の巡回置換である。ここで、 b_{i} \ge a_{i+1}となるiが存在するなら、置換(p_{1}, ... , p_{i+1}, p_{i}, ... p_{N})は条件を満たす。 なぜなら、(p_{1}, ... , p_{i+1}, p_{i}, ... p_{N}) = p(p_{i}, p_{i+1})であり、pp(p_{i}, p_{i+1})は偶奇が異なるが、n要素の置換は高々n-1個の互換に分解できるので、p(p_{i}, p_{i+1})はn-1個より少ない数の互換の積で表せるはずだからである。一方、 b_{i} \ge a_{i+1}となるiが存在しないなら、 b_{i} \ge a_{i} を満たすような置換はpのみである。

pがいくつの巡回置換に分解できるかはUnion-Find木を用いて求めることができる。

...

#define rep(i, n) for (int64_t i = 0; i < (n); i++)

class UFTree{ //Union-Find木
    ...
};

int main()
{
    int n;
    cin >> n;

    using P = tuple<int, int>;
    vector<int> a(n), b(n);
    vector<P> p(n);
    rep(i, n)
    {
        cin >> a[i];
    }
    rep(i, n)
    {
        cin >> b[i];
    }

    rep(i, n)
    {
        p[i] = P(b[i], a[i]);
    }
    sort(p.begin(), p.end());

    vector<P> q(n);
    rep(i, n)
    {
        int c;
        tie(ignore, c) = p[i];
        q[i] = P(c, i);
    }

    sort(q.begin(), q.end());

    rep(i, n)
    {
        int c, d;
        tie(c, ignore) = q[i];
        tie(d, ignore) = p[i];
        if (d < c) {
            cout << "No" << endl;
            return 0;
        }
    }

    UFTree uft(n);
    rep(i, n)
    {
        int j;
        tie(ignore, j) = q[i];
        uft.merge(i, j);
    }

    int cnt = 0;
    vector<bool> isCounted(n, false);
    rep(i, n)
    {
        if (!isCounted[uft.root(i)]) {
            cnt++;
            isCounted[uft.root(i)] = true;
        }
    }

    if (cnt > 1) {
        cout << "Yes" << endl;
    } else {
        rep(i, n - 1)
        {
            int a, b;
            tie(b, ignore) = p[i];
            tie(a, ignore) = q[i + 1];
            if (b >= a) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
    }

    return 0;
}

コンテスト中は何故か場合分けする発想がなくて解けなかった。