ARC124-D Yet Another Sorting Problem 解説

問題概要

$\{1, \ldots, N + M\}$ の順列 $p = (p_1, \ldots, p_{N+M})$ が与えられる。 $i, j\ (1\le i \le N, 1\le j \le M)$ を選び、 $p_i$ と $p_{N+j}$ をswapする操作を任意の回数行う。順列を $(1, \ldots, N+M)$ にソートするために必要な操作の最小回数を求めよ。

思考過程

$p_1, \ldots, p_N$ と $p_{N+1}, \ldots, p_M$ を左右に分けてサンプル2を書いてみる。順列なので、とりあえずサイクルごとに色分けして矢印を引いてみた。それぞれのサイクルが何回の操作で元に戻せるかをみると、左右にまたがったサイズ $r$ のサイクル（タイプ1と呼ぶ）は $r - 1$ 回の操作で正しい位置に戻せるが、サンプル2における $\{8, 10\}$ のように、右側（あるいは左側）の頂点だけからなるサイクル（タイプ2と呼ぶ）は解消に $r + 1$ 回かかることがわかる。タイプ2のサイクルの解消過程は、もう片側の頂点を含むようなサイズ $s$ のサイクルと辺を交換してタイプ1のサイクルに変化させ、 $r + s - 1$ 回かけてそれを解消するということをしている。タイプ2のサイクルたちをどのように解消すれば回数を減らせるかを考えると、タイプ2のサイクルが両側にある場合、それらの間で辺を交換することで、 $1 + (s + r - 1)$ 回で2つのサイクルが解消できて、これがもっとも経済的に見える。

結局、

両側にタイプ2のサイクルがある限り、それらの間で辺を交換してタイプ1のサイクルに変換する。
タイプ1のサイクルをすべて解消する。
残ったタイプ2のサイクルをすべて解消する。

という戦略を考えた。この戦略の最小性の証明はできなかったが、合ってそうだったので提出したら通った。証明は公式解説が分かりやすい。

実装

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; cin >> n >> m;
    vector<int> p(n + m);
    for(int i = 0; i < n + m; ++i){
        cin >> p[i];
        p[i]--;
    }
    vector<int> seen(n + m, 0);
    vector<vector<int>> cycles;
    for(int i = 0; i < n + m; ++i){
        if(seen[i]) continue;
        int now = i;
        vector<int> temp;
        while(!seen[now]){
            seen[now] = true;
            temp.push_back(now);
            now = p[now];
        }
        cycles.push_back(temp);
    }
    vector<vector<int>> left, right, both;
    for(auto c : cycles){
        if(c.size() == 1) continue;
        bool l = false, r = false;
        for(int i : c){
            if(i < n) l = true;
            if(i >= n) r = true;
        }
        if(l and r) both.push_back(c);
        else if(l) left.push_back(c);
        else right.push_back(c);
    }
    int ans = 0;
    for(auto c : both) ans += c.size() - 1;
    for(auto c : left) ans += c.size() + 1;
    for(auto c : right) ans += c.size() + 1;
    ans -= 2 * min(left.size(), right.size());
    cout << ans << '\n';
}

感想

公式解説の証明思いつける気がしないので、これ本番中に解いた人はどうやって正当性を示したか教えてほしいです。