Pythonで「1」をすべてグループ化するために必要な最小スワップ回数を求めるプログラム

問題の概要

バイナリ文字列（0と1のみで構成された文字列）が与えられたとき、すべての「1」を文字列内の任意の位置にまとめてグループ化するために必要な最小スワップ回数を求めます。

例えば、入力が "10101001101" の場合、出力は 3 になります。「00000111111」のように並べ替えることで、わずか3回のスワップですべての1を隣接させることができるためです。

解法のアプローチ：スライディングウィンドウと累積和

この問題は、スライディングウィンドウ（尺取り法）と累積和（プレフィックスサム）を組み合わせることで効率的に解けます。基本的な考え方は次の通りです。

文字列中の1の総数を one とすると、最終的な目標は長さ one の区間にすべての1を集めることです。そこで、長さ one のウィンドウを左端から順にスライドさせながら、各ウィンドウ内に含まれる0の個数（＝必要なスワップ回数）を累積和を使って高速に計算します。ウィンドウ内の0の数が最小となる位置が答えになります。

具体的な手順

1. 与えられた文字列を整数のリスト data に変換します。
2. 変数 one を 0 で初期化し、n を配列 data の長さとします。
3. サイズ n の累積和配列 summ を作成し、すべて 0 で埋めた後、summ[0] := data[0] とします。
4. one := one + data[0] として1の個数のカウントを開始します。
5. i が 1 から n−1 までの範囲で以下を繰り返します。
   • summ[i] := summ[i-1] + data[i]
   • one := one + data[i]
6. ans := one で初期化します。
7. left := 0、right := one - 1 とし、ウィンドウの両端を設定します。
8. right < n の間、以下を繰り返します。
   • left が 0 の場合は temp := summ[right]、それ以外の場合は temp := summ[right] - summ[left-1] としてウィンドウ内の1の個数を取得します。
   • ans := min(ans, one - temp) で最小スワップ回数を更新します（one - temp はウィンドウ内の0の個数に相当します）。
   • right と left をそれぞれ 1 ずつ増やしてウィンドウをスライドさせます。
9. ans を返します。

実装例

以下にPythonでの実装例を示します。

サンプルコード

class Solution(object):
    def solve(self, data):
        data = list(map(int, list(data)))
        one = 0
        n = len(data)
        summ = [0 for i in range(n)]
        summ[0] = data[0]
        one += data[0]
        for i in range(1, n):
            summ[i] += summ[i-1] + data[i]
            one += data[i]
        ans = one
        left = 0
        right = one - 1
        while right < n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans, one - temp)
            right += 1
            left += 1
        return ans

ob = Solution()
print(ob.solve("10101001101"))

入力

"10101001101"

出力

3

計算量について

このアルゴリズムでは、累積和の構築に O(n)、ウィンドウのスライドにも O(n) しかかからないため、全体の計算量は O(n) となります。素朴に全ての並べ替えを試す方法と比べて非常に効率的であり、長いバイナリ文字列に対しても実用的な速度で動作します。