C++でスライディングウィンドウ法を使い、連続する1が最大になるように反転すべき0を見つける方法

このチュートリアルでは、配列内の一部の0（ゼロ）を1に反転したときに、連続する1の数が最大になるように、どの0を反転すべきかを見つける方法を解説します。

この問題はスライディングウィンドウ（Sliding Window）と呼ばれる手法を使うことで、O(n) の計算量で効率的に解くことができます。それでは、具体的な手順を見ていきましょう。

アルゴリズムの手順

• 対象となる配列と、反転できる0の最大数（maxZeroes）を初期化します。

• ウィンドウの開始インデックス（start）、終了インデックス（end）、およびウィンドウの長さを初期化します。

• 連続する1の最長部分配列の長さと、その開始インデックスを記録しておきます。

• 終了インデックスが配列の長さを超えるまで、配列を反復処理します。

• 0のカウントが maxZeroes 未満の場合は、終了インデックスを進めます。その際、現在の要素が0であれば0のカウントを増やします。

• 0のカウントが maxZeroes を超えた場合は、開始インデックスを進めます。その際、現在の要素が0であれば0のカウントを減らします。

• 現在のウィンドウの長さがこれまでの最大値より大きければ、最大ウィンドウの情報を更新します。

• 最後に、記録したウィンドウの開始インデックスをもとに配列を走査し、反転すべき0のインデックスを出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void zeroesIndexes(int arr[], int maxZeroes, int n) {
    int start = 0, end = 0;
    int zeroesCount = 0;
    int bestWindowCount = 0, bestWindowStartIndex = 0;
    while (end < n) {
        if (zeroesCount <= maxZeroes) {
            if (arr[end] == 0) {
                zeroesCount++;
            }
            end++;
        }
        if (zeroesCount > maxZeroes) {
            if (arr[start] == 0) {
                zeroesCount--;
            }
            start++;
        }
        if ((end - start > bestWindowCount) && (zeroesCount <= maxZeroes)) {
            bestWindowCount = end - start;
            bestWindowStartIndex = start;
        }
    }
    cout << "The indexes are ";
    for (int i = 0; i < bestWindowCount; ++i) {
        if(arr[bestWindowStartIndex + i] == 0)
            cout << bestWindowStartIndex + i << " ";
    }
}
int main() {
    int arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1};
    int maxZeroes = 2;
    zeroesIndexes(arr, maxZeroes, 10);
    return 0;
}

実行結果

上記のコードを実行すると、次のような出力が得られます。

The indexes are 5 7

この例では、配列 {1, 0, 0, 1, 1, 0, 1, 0, 1, 1} のうち、インデックス5と7の0を反転することで、最も長い連続する1（長さ6）が得られることがわかります。

まとめ

スライディングウィンドウ法を活用することで、配列全体を何度も走査することなく、一度の走査で最適な反転位置を見つけられることがお分かりいただけたかと思います。本チュートリアルについてご不明な点がある場合は、ぜひコメント欄でお知らせください。