C++で隣接要素を埋める最小反復回数により配列を1で満たす方法

この問題では、0または1のいずれかで構成されるn個の要素を持つ配列arrが与えられます。求められているのは、「隣接要素を埋める」という操作を最小の反復回数で実行し、配列全体を1で満たすことです。

例で問題を理解する

入力：arr[] = {0, 1, 1, 0, 0, 1}

出力：1

この場合、インデックス3〜4に連続する2つの0は、両側の1から同時に伝播することで1回の反復で埋められるため、答えは1となります。

解法アプローチ

この問題を解くうえで重要なのは、「ある位置に1が存在すれば、その両隣の2つの0を1に変換できる」という性質です。

もし arr[i] が 1 ならば、
arr[i-1] と arr[i+1] は 1 に変換されます。

この性質を利用すると、配列を「0が連続する区間（ブロック）」ごとに分割し、ブロックごとに必要な反復回数を求めて、その最大値を答えとすればよいことが分かります。ブロックの状態に応じて、次の3つのケースに分けて考えます。

ケース1：ブロックの両側に1がある場合

ブロックの先頭と末尾が1で、それ以外がすべて0のケースです。まず0の個数（zeroCount）を数えます。両側から同時に伝播が進むため、1回の反復で2つの0を埋められます。

• zeroCount が偶数の場合：反復回数 = zeroCount / 2
• zeroCount が奇数の場合：反復回数 = (zeroCount + 1) / 2

ケース2：ブロックの片側にしか1がない場合

ブロックの先頭または末尾にだけ1があり、残りがすべて0のケース（配列の端に0が連続している場合）です。伝播が一方向からしか進まないため、0の個数ぶんの反復が必要になります。

反復回数 = zeroCount

ケース3：ブロック内に1がひとつもない場合

配列全体が0の場合、1を新たに生み出すことはできません。この場合は -1 を出力し、「1で埋めることは不可能」であることを示します。

解法の動作を示すプログラム

#include <iostream>
using namespace std;

int countIterationFill1(int arr[], int n) {

    bool oneFound = false;
    int iterationCount = 0;
    for (int i = 0; i < n; ) {

        if (arr[i] == 1)
            oneFound = true;
        // 連続する1を読み飛ばす
        while (i < n && arr[i] == 1)
            i++;
        // 連続する0の個数を数える
        int zeroCount = 0;
        while (i < n && arr[i] == 0) {
            zeroCount++;
            i++;
        }
        // 配列全体が0の場合は1で埋められない
        if (!oneFound && i == n)
            return -1;
        int itrCount;
        if (i < n && oneFound) {
            // ケース1：両側が1に囲まれた0のブロック
            itrCount = (zeroCount + 1) / 2;
        } else {
            // ケース2：片側だけに1がある（配列の端の）ブロック
            itrCount = zeroCount;
        }
        iterationCount = max(iterationCount, itrCount);
    }

    return iterationCount;
}

int main() {

    int arr[] = {0, 1, 1, 0, 0, 1, 0, 0, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "1で埋めるために必要な反復回数: " << countIterationFill1(arr, n);
    return 0;
}

出力

1で埋めるために必要な反復回数: 2

実行結果の解説

サンプル配列 {0, 1, 1, 0, 0, 1, 0, 0, 0, 1} には、0のブロックが2つあります。インデックス3〜4の「00」は両側が1に囲まれているため 2 / 2 = 1 回、インデックス6〜8の「000」も両側が1に囲まれているため (3 + 1) / 2 = 2 回かかります。配列全体が1になるのは、最も時間のかかるブロックが埋まりきったときなので、答えは最大値の2となります。

計算量

• 時間計算量：O(n) ― 配列を一度走査するだけで済みます。
• 空間計算量：O(1) ― 追加の配列は不要です。