Pythonで長さkの部分リスト反転により全要素を0にする最小操作回数を求めるプログラム

問題の概要

0と1のみで構成された数値のリスト nums と、整数 k が与えられます。

ここで、「長さkの部分リスト(サブリスト)を選んで反転する」という操作を考えます。反転を行うと、その範囲内のすべての1は0に、0は1に変わります。この操作を繰り返して、リスト内のすべての1を0にするために必要な最小の操作回数を求めてください。どのように操作してもすべてを0にできない場合は -1 を返します。

例えば、nums = [1,1,1,0,0,1,1,1]、k = 3 の場合、出力は 2 になります。これは、先頭の3つの要素を反転して0にし、次に末尾の3つの要素を反転して0にできるためです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• n := nums のサイズ
• res := 0(操作回数のカウント)、flipped := 0(現在の反転状態)
• to_conv := サイズnのリストを0で初期化(反転の影響が終わる位置を記録)
• i を 0 から n-1 まで繰り返す:
  • flipped := flipped XOR to_conv[i]
  • cur := nums[i]
  • cur := cur XOR flipped
  • cur が 1 の場合:
    • flipped := flipped XOR 1
    • res := res + 1
    • i + k - 1 >= n の場合は -1 を返す(残りの範囲で反転できないため)
    • i + k < n の場合は to_conv[i + k] := 1 を設定
• 最後に res を返す

アルゴリズムのポイント

このアルゴリズムの鍵となるのは、XOR(排他的論理和)による反転状態の効率的な管理です。各ステップで実際にリストを書き換える代わりに、「現時点でこの位置が反転済みかどうか」を flipped 変数で追跡します。さらに、反転操作の影響が終了する位置(i + k)を to_conv リストに記録しておき、その位置に到達した時点で反転状態を解除します。これにより、各要素を一度だけ処理すればよくなり、全体を線形時間で解くことが可能になります。

実装例

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

class Solution:
   def solve(self, nums, k):
      n = len(nums)
      res = 0
      flipped = 0
      to_conv = [0] * n
      for i in range(n):
         flipped ^= to_conv[i]
         cur = nums[i]
         cur ^= flipped
         if cur == 1:
            flipped ^= 1
            res += 1
            if i + k - 1 >= n:
               return -1
            if i + k < n:
               to_conv[i + k] = 1
      return res
ob = Solution()
nums = [1,1,1,0,0,1,1,1]
k = 3
print(ob.solve(nums, k))

入力

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

出力

2

計算量の分析

時間計算量: O(n) — リストを一度だけ走査するため、要素数に対して線形時間で処理できます。
空間計算量: O(n) — 反転終了位置を記録するための補助リスト to_conv が必要です。

素朴なアプローチでは各反転ごとにk個の要素を書き換える必要があり、最悪の場合 O(n×k) の時間がかかりますが、このXORを使った手法なら大規模な入力でも高速に動作します。