C++で靴下のペアをすべて隣り合わせに並べ替える！最小スワップ回数を求めるプログラム

問題概要

一列に並んだ靴下を表す数値のリスト row が与えられます。靴下には 0 から順に番号が振られており、(0, 1)、(2, 3)、(4, 5) のように「偶数番号とその次の番号」が同じペアになっています。現状では靴下はバラバラに置かれているため、各ペアが必ず隣り合うように並べ替えたいと考えます。このとき必要となるスワップ（要素の入れ替え）の最小回数を求めるのがこの問題の目的です。

入力例と並べ替えの流れ

たとえば、入力が row = [0, 5, 6, 2, 1, 3, 7, 4] の場合、並べ替えの過程は次のようになります。

• [0, 5, 6, 2, 1, 3, 7, 4]（初期状態）
• [0, 1, 6, 2, 5, 3, 7, 4]（1 回目のスワップ：0 と 1 を隣接させる）
• [0, 1, 3, 2, 5, 6, 7, 4]（2 回目のスワップ：2 と 3 を隣接させる）
• [0, 1, 3, 2, 5, 4, 7, 6]（3 回目のスワップ：残りのペアも隣接させる）

このように、すべてのペアが隣り合った状態になるまでのスワップ回数が答えとなります。

アルゴリズムの考え方（Union-Find）

この問題は Union-Find（素集合データ構造） を使うと効率的に解けます。ポイントは次のとおりです。

• 靴下番号 k に対して k / 2（小数点以下切り捨て）が、その靴下の属するペアのグループ番号になります（例：靴下 4 と 5 はどちらもグループ 2）。
• 現在の並びで「同じ隣接スロットに入っている 2 枚の靴下」同士を結ぶ辺をグラフに追加していきます。
• こうしてできる各連結成分について、「成分のサイズ − 1」回のスワップが必要になります。
• したがって、答えはすべての連結成分に対する (サイズ − 1) の総和です。

解法の手順

1. 親を管理する配列 p と、各集合のサイズを管理する配列 sz を用意します。
2. 関数 find(u) を定義します。p[u] == u なら u を返し、そうでなければ再帰的に根を探しながら経路圧縮（p[u] = find(p[u])）を行います。
3. 関数 join(u, v) を定義します。pu = find(u)、pv = find(v) を求め、同一集合なら何もしません。sz[pu] >= sz[pv] なら pv を pu 側へ、そうでなければ pu を pv 側へ併合します（union by size）。
4. メイン処理では n = 配列サイズ ÷ 2（ペアの総数）とし、p[i] = i で初期化、sz はすべて 1 で初期化します。
5. i 番目の隣接スロットにある 2 枚の靴下 arr[2i] と arr[2i+1] について、それぞれ 2 で割ってグループ番号 u, v を求め、join(u, v) を呼び出します。
6. 最後に、各 i について find(i) == i（自分が根）であれば ans += sz[i] - 1 を加算し、ans を返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
vector<int> p, sz;

int find(int u) {
    return p[u] == u ? u : p[u] = find(p[u]);
}

void join(int u, int v) {
    int pu = find(u), pv = find(v);
    if (pu == pv)
        return;
    if (sz[pu] >= sz[pv]) {
        p[pv] = pu;
        sz[pu] += sz[pv];
    } else {
        p[pu] = pv;
        sz[pv] += sz[pu];
    }
}

int solve(vector<int>& arr) {
    int n = arr.size() / 2;
    p = vector<int>(n);
    for (int i = 0; i < n; ++i)
        p[i] = i;
    sz = vector<int>(n, 1);
    for (int i = 0; i < n; ++i) {
        int u = arr[i << 1] / 2;
        int v = arr[i << 1 | 1] / 2;
        join(u, v);
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (find(i) == i)
            ans += sz[i] - 1;
    return ans;
}

int main() {
    vector<int> v = {0, 5, 6, 2, 1, 3, 7, 4};
    cout << solve(v);
}

実行結果

3

計算量

Union-Find に経路圧縮と union by size を組み合わせているため、各操作はほぼ定数時間（アッカーマン逆関数 α(N)）で処理できます。全体の計算量は O(N α(N)) となり、N は靴下の本数です。これは事実上 N に比例する非常に効率的な手法です。

まとめ

靴下をペア単位でグループ化し、Union-Find で連結成分を求めることで、最小スワップ回数を高速に計算できます。「各連結成分のサイズから 1 を引いた値の総和」というシンプルな公式がこの問題の鍵です。