C++ですべての1をグループ化するために必要な最小スワップ回数を求める方法

問題の概要

0と1のみで構成された配列が与えられます。この配列内に存在するすべての「1」を連続したブロックとしてまとめる（グループ化する）ために必要な、最小のスワップ（要素の入れ替え）回数を求めるのが課題です。

例

入力配列が {1, 0, 1, 1, 0, 1} の場合、必要なスワップ回数は 1回 です。先頭の0と末尾の1を入れ替えることで、すべての1を連続して並べることができます。

アルゴリズムの考え方

この問題は、次の手順で効率的に解くことができます。

• まず、配列内の1の総数を数えます。これを x とします。
• すべての1をグループ化すると、最終的に長さ x の連続した区間に1が集まることになります。したがって、長さ x の部分配列（ウィンドウ）の中で、1の個数が最大になるものを探します。
• 必要な最小スワップ回数は、そのウィンドウに含まれる0の個数、すなわち「x − ウィンドウ内の1の個数」となります。

各ウィンドウ内の1の個数を高速に求めるために、累積和（プレフィックスサム）を前計算しておきます。これにより、任意の区間の1の個数をO(1)で取得でき、配列全体を一度の走査で処理できます。これはいわゆる「スライディングウィンドウ」と呼ばれる定番のテクニックです。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int getMinSwaps(int *arr, int n) {
    int oneCnt = 0;
    for (int i = 0; i < n; ++i) {
        if (arr[i] == 1) {
            ++oneCnt;
        }
    }
    int x = oneCnt;
    int maxOnes = INT_MIN;
    int preCompute[n] = {0};
    if (arr[0] == 1) {
        preCompute[0] = 1;
    }
    for (int i = 1; i < n; ++i) {
        if (arr[i] == 1) {
            preCompute[i] = preCompute[i - 1] + 1;
        } else {
            preCompute[i] = preCompute[i - 1];
        }
    }
    for (int i = x - 1; i < n; ++i) {
        if (i == (x - 1)) {
            oneCnt = preCompute[i];
        } else {
            oneCnt = preCompute[i] - preCompute[i - x];
        }
        if (maxOnes < oneCnt) {
            maxOnes = oneCnt;
        }
    }
    int swapCnt = x - maxOnes;
    return swapCnt;
}

int main() {
    int arr[] = {1, 0, 1, 1, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum swap count = " << getMinSwaps(arr, n) << endl;
    return 0;
}

コードのポイントは以下の通りです。

• oneCnt：配列全体の1の個数（ウィンドウの長さ x）を表します。
• preCompute：累積和の配列で、preCompute[i] はインデックス0からiまでの1の個数を保持します。
• 長さ x の各ウィンドウについて、累積和の差分から1の個数を求め、最大値 maxOnes を更新していきます。
• 最終的な答えは「x − maxOnes」、つまり最適なウィンドウ内の0の個数です。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum swap count = 1

計算量

• 時間計算量： O(n) — 配列を数回走査するだけで完了します。
• 空間計算量： O(n) — 累積和の配列を保持するために必要です。

このように、累積和とスライディングウィンドウを組み合わせることで、全ての1をグループ化するための最小スワップ回数を線形時間で効率よく求めることができます。