【C++】配列を「美しい配列」にするために必要な最小操作回数を求めるアルゴリズム

本記事では、0と1のみで構成される長さnの2進数配列bin[]が与えられたとき、この配列を「美しい配列」に変換するために必要な最小操作回数を求める方法を解説します。

「美しい配列」とは、0と1が交互に並ぶパターンを持つ特殊な2進数配列のことです。

問題の概要

配列を美しい配列にするために必要な操作回数を求めます。1回の操作は、次の3つのステップで構成されます。

• ステップ1：配列を前半と後半の2つに分割する
• ステップ2：どちらか一方の半分を反転させる
• ステップ3：分割した2つを再び連結する

この操作を何回繰り返せば配列が美しい配列になるかをカウントします。

具体例で理解しよう

入力

bin[] = {1, 0, 1, 0, 0, 1}

出力

1

説明

後半の部分配列bin[4, 5]を切り出して反転させ、再び連結します。これにより配列は{1, 0, 1, 0, 1, 0}という完全な交互パターンになり、必要な操作はわずか1回です。

解法アプローチ

この問題の解法は、「必要な最小操作回数は、隣り合う2つの要素がともに0である箇所（連続ゼロペア）の数と等しい」という性質に基づいています。

まず、次の基本ケースを確認しましょう。

• 配列のサイズが1の場合：単一要素の配列は常に美しい配列なので、操作は不要です。
• 配列のサイズが奇数の場合：0と1を交互に並べるには偶数個の要素が必須のため、美しい配列にすることは不可能です。

それ以外の偶数の長さの場合は、隣接する要素がともに0になっている箇所の総数を数え上げます。この数がそのまま実行すべき操作回数になります。

アルゴリズム

初期化：consZero = 0（連続ゼロペアのカウンタ）

1. ステップ1：n == 1 の場合は 0 を返す
2. ステップ2：n % 2 != 0（奇数長）の場合は -1 を返す
3. ステップ3：i を 0 から n-1 までループする
   ステップ3.1：bin[i] == 0 かつ bin[i+1] == 0 ならば consZero++
4. ステップ4：bin[n-1] == 0 かつ bin[0] == 0（配列の末尾と先頭にまたがるペア）ならば consZero++
5. ステップ5：consZero の値を返す

C++での実装例

#include <iostream>
using namespace std;

int minOperations(int bin[], int n) {
    if (n == 1)
        return 0;
    if (n % 2 != 0)
        return -1;

    int consZero = 0;
    for (int i = 0; i < n; ++i) {
        if (i + 1 < n) {
            if (bin[i] == 0 && bin[i + 1] == 0)
                consZero++;
        }
    }
    if (bin[0] == bin[n - 1] && bin[0] == 0)
        consZero++;

    return consZero;
}

int main() {
    int bin[] = { 1, 0, 1, 0, 0, 1 };
    int n = sizeof(bin) / sizeof(bin[0]);
    cout << "配列を美しくするために必要な最小操作回数: "
         << minOperations(bin, n);
    return 0;
}

出力

配列を美しくするために必要な最小操作回数: 1

計算量

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量はO(n)、追加の記憶領域もカウンタ変数程度で済み、空間計算量はO(1)と非常に効率的です。