C++で解く「カップルの手つなぎ」問題 ― 最小スワップ回数を求めるアルゴリズム

問題の概要

N組のカップルが、一列に並んだ2N個の座席に座っており、それぞれパートナーと隣り合って手をつなぎたいと考えています。すべてのカップルが隣同士に座る状態を作るために必要な、最小のスワップ（入れ替え）回数を求めましょう。

人と座席は0から2N-1までの番号で表されます。カップルには順に番号が割り当てられており、1組目は(0, 1)、2組目は(2, 3)、最後のN組目は(2N-2, 2N-1)というペアになります。

初期状態の着席情報は配列rowとして与えられ、row[i]にはi番目の座席に最初に座っている人の番号が入っています。

たとえば入力が [0, 2, 4, 1, 3, 5] の場合、答えは 2 になります。これは、2回のスワップですべてのカップルを隣り合わせにできることを意味します。

解法の考え方：Union-Find（素集合データ構造）

この問題は、Union-Find（ユニオン・ファインド）を使うと効率的に解けます。ポイントは「人を2人ずつのグループ単位で捉える」という発想です。

人の番号を2で割ると、同じカップルは必ず同じグループ番号になります。つまり(0, 1)はグループ0、(2, 3)はグループ1といった具合です。隣り合う2座席に座っている2人が別々のカップルに属している場合、そのグループ同士をつなげていくと、連結成分（グラフのつながり）が形成されます。

ここで重要な性質として、サイズkの連結成分をバラバラのカップル単位に並べ替えるには k−1 回のスワップが必要です。したがって、全体の最小スワップ回数は次の式で求められます。

最小スワップ回数 ＝ カップルの総数N − 連結成分の数

アルゴリズムの手順

1. UF（Union-Find）クラスを定義し、内部にparent配列を持たせます。
2. Nを引数にUFを初期化します。count := N とし、parent[i] := i（自分自身を親とする）を設定します。
3. unionn(a, b)：aとbの根parA、parBを取得します。両者が同じなら何もしません。異なる場合はcountを1減らし、parent[parB] := parA としてマージします。
4. getParent(i)：parent[i] == i ならiを返します。そうでなければ再帰的に根を求め、同時に経路圧縮も行います（return parent[i] = getParent(parent[i])）。
5. メイン処理では、n := rowのサイズ、N := n / 2 とします。
6. UFインスタンスufをNで初期化します。
7. gr := 0 から N-1 までループし、a := row[gr * 2]、b := row[gr * 2 + 1] を取り出して、uf.unionn(a / 2, b / 2) を呼び出します。
8. 最後に N − uf.count を返します。これが求める最小スワップ回数です。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    class UF{
    public:
        vector<int> parent;
        int count;
        UF(int N){
            count = N;
            parent = vector<int>(N);
            for (int i = 0; i < N; i++) {
                parent[i] = i;
            }
        }
        void unionn(int a, int b){
            int parA = getParent(a);
            int parB = getParent(b);
            if (parA == parB)
                return;
            count--;
            parent[parB] = parA;
        }
        int getParent(int i){
            if (parent[i] == i)
                return i;
            return parent[i] = getParent(parent[i]);
        }
    };
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int N = n / 2;
        UF uf(N);
        for (int gr = 0; gr < N; gr++) {
            int a = row[gr * 2];
            int b = row[gr * 2 + 1];
            uf.unionn(a / 2, b / 2);
        }
        return N - uf.count;
    }
};
main(){
    Solution ob;
    vector<int> v = {0,2,4,1,3,5};
    cout << (ob.minSwapsCouples(v));
}

入力

{0,2,4,1,3,5}

出力

2

まとめ

この問題は、カップルを「グループ」単位で捉え、Union-Findで連結成分を数えることで、最小スワップ回数をほぼ線形時間（O(N α(N))、αは事実上定数のアッカーマン逆関数）で求められます。複雑なシミュレーションを必要とせず、「N − 連結成分の数」というシンプルな式に帰着できるのが大きな魅力です。競技プログラミングでも頻出のテクニックなので、ぜひマスターしておきましょう。