C++で解く「K個の連続するビットフリップ」問題：最小反転回数の求め方

問題概要

0と1のみから構成される配列Aが与えられます。「Kビットフリップ」とは、長さKの連続する部分配列をひとつ選び、その範囲内のすべてのビットを同時に反転させる操作のことです。この操作を繰り返し、配列内に0が一つも残らない状態を目指します。必要となる最小のKビットフリップの回数を求めてください。ただし、どのように操作しても達成できない場合は -1 を返します。

入出力例

入力が [0,0,0,1,0,1,1,0]、K = 3 の場合、答えは 3 になります。次の手順で操作することで、すべての要素を1にできます。

• 1回目：A[0]〜A[2] をフリップ → 配列は [1,1,1,1,0,1,1,0] になります
• 2回目：A[4]〜A[6] をフリップ → 配列は [1,1,1,1,1,0,0,0] になります
• 3回目：A[5]〜A[7] をフリップ → 配列は [1,1,1,1,1,1,1,1] となり完成です

解き方のアプローチ

この問題を素朴に解こうとすると、フリップのたびに実際に区間を書き換える必要があり、計算量が膨れ上がってしまいます。そこで役立つのが差分配列の考え方です。各位置が「これまでに何回フリップの影響を受けたか」を累積和で管理すれば、ビットを実際に書き換えることなく、偶数回フリップされたのか奇数回フリップされたのかを即座に判定できます。

具体的な手順は以下の通りです。

• n := 配列Aのサイズとします
• サイズnの配列 moves を定義します（フリップの開始・終了を記録する配列）
• counter := 0 で初期化します（フリップ回数のカウンタ）
• i := 0 から開始し、i + K ≤ n である限り i を1ずつ増やしながら以下を繰り返します。
  • i > 0 の場合：moves[i] := moves[i] + moves[i-1]
  • ((moves[i] mod 2) + A[i]) mod 2 が 0 のとき（＝フリップ後もビットが0のままのとき）：
    • moves[i] := moves[i] + 1
    • i + K < n の場合：moves[i + K] -= 1
    • counter を1増やします
• 続いて、末尾側の残りの要素（i < n）に対しても同じ判定を行います。
  • i > 0 の場合：moves[i] := moves[i] + moves[i-1]
  • ((moves[i] mod 2) + A[i]) mod 2 が 0 のままであれば、もうフリップを適用できないため return -1
• 最後に counter を返します

ポイントは、位置 i を起点にフリップを行う際に moves[i] を +1、moves[i+K] を -1 しておく点です。こうすることで累積和を取るだけで、任意の位置に及ぶフリップの総回数とその偶奇を把握できます。また、長さKのフリップを開始できるのは i + K ≤ n の範囲だけなので、末尾側では検証のみを行い、0が残っていた場合は -1 を返します。

C++による実装例

それでは、上記のアルゴリズムをC++で実装したコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minKBitFlips(vector<int>& A, int K){
        int n = A.size();
        vector<int> moves(n);
        int i;
        int counter = 0;
        for (i = 0; i + K <= n; i++) {
            if (i > 0)
            moves[i] += moves[i - 1];
            if (!(((moves[i] % 2) + A[i]) % 2)) {
                moves[i] += 1;
                if (i + K < n)
                    moves[i + K] -= 1;
                counter++;
            }
        }
        for (; i < n; i++) {
            if (i > 0)
            moves[i] += moves[i - 1];
            if (!(((moves[i] % 2) + A[i]) % 2))
                return -1;
        }
        return counter;
    }
};
main(){
    Solution ob;
    vector<int> v = {0,0,0,1,0,1,1,0};
    cout << (ob.minKBitFlips(v, 3));
}

入力

{0,0,0,1,0,1,1,0}, 3

出力

3

まとめ

本問題は、差分配列と累積和を組み合わせることで、配列の書き換えを伴わずに各区間へのフリップの影響を追跡できました。時間計算量は O(n)、空間計算量も O(n) であり、大規模な入力に対しても効率的に動作します。区間更新を扱うビット操作系の問題では頻出のテクニックなので、ぜひマスターしておきましょう。