Pythonでバイナリ配列にk個の連続する1を作るための最小隣接スワップ回数を求めるプログラム

問題概要

0と1のみから構成されるバイナリ配列 nums と整数 k が与えられます。1回の操作では、隣り合う2つの要素を選んで値を入れ替える（スワップする）ことができます。配列の中に k個の連続する1 が存在する状態を作るために必要な最小の操作回数を求めるのが、この問題の目的です。

例えば、入力が nums = [1,0,0,1,0,1,0,1]、k = 3 の場合を考えてみましょう。このときの出力は 2 となります。1回目のスワップで [1,0,0,1,0,1,0,1] から [1,0,0,0,1,1,0,1] へ並べ替え、さらに2回目のスワップで [1,0,0,0,1,1,1,0] とすることで、3個の連続した1が完成するからです。

解法のアプローチ

この問題は、「1」が出現する位置（インデックス）を記録しながらスライディングウィンドウで管理することで、効率的に解くことができます。重要なポイントは、k個の1を1か所に集める際のコストは、ウィンドウ内の中央値（メジアン）を基準としたときに最小になるという性質です。新しい1を見つけるたびにコストを差分更新し、ウィンドウサイズがkを超えたら左端の要素を取り除くことで、配列全体を一度の走査で処理できます。

アルゴリズムの手順

• j := 0（ウィンドウの左端ポインタ）、val := 0（現在のコスト合計）、ans := 999999（答えの初期値）として初期化します。
• 「1」の位置を保存するための空のリスト loc を用意します。
• 配列 nums の各インデックス i と値 x に対して、以下の処理を行います。
  • x が 0 以外である場合：
    • インデックス i を loc の末尾に追加します。
    • m := (j + locの長さ − 1) ÷ 2（切り捨て除算）とし、val に loc[-1] − loc[m] − (locの長さ − j) ÷ 2 を加算します。
    • locの長さ − j が k より大きい場合は、m := (j + locの長さ) ÷ 2 として、val から loc[m] − loc[j] − (locの長さ − j) ÷ 2 を減算し、j を 1 増やします（ウィンドウの左端を縮める）。
    • locの長さ − j がちょうど k と等しい場合、ans を ans と val の小さい方で更新します。
• 最後に ans を返します。

実装例

理解を深めるために、以下のPython実装を見てみましょう。

def solve(nums, k):
   j = val = 0
   ans = 999999
   loc = []
   for i, x in enumerate(nums):
      if x:
         loc.append(i)
         m = (j + len(loc) - 1)//2
         val += loc[-1] - loc[m] - (len(loc)-j)//2
         if len(loc) - j > k:
            m = (j + len(loc))//2
            val -= loc[m] - loc[j] - (len(loc)-j)//2
            j += 1
         if len(loc)-j == k:
            ans = min(ans, val)
   return ans

nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))

入力

[1,0,0,1,0,1,0,1], 3

出力

2

計算量について

配列を一度だけ走査し、各ステップの更新処理はすべて定数時間で行われるため、時間計算量は O(n) です。また、補助的に使用するリスト loc のサイズは「1」の個数に依存するため、空間計算量も O(n) となります。すべての連続区間を毎回ゼロから計算し直す方法と比べ、コストを差分更新していくこの手法は非常に効率的です。