C++で配列のすべての値を1にするための最小右フリップ回数を求める

同じ配線に直列に接続された電球のON/OFF状態を、0と1からなる配列で表現します。0は消灯(OFF)、1は点灯(ON)を意味します。このようなN個の電球の並びにおいて、ある電球のスイッチを押すと、その右側にあるすべての電球(i+1番目からn番目まで)の状態が反転し、ONだった電球はOFFに、OFFだった電球はONに変わります。

与えられた電球の状態をもとに、すべての電球を点灯させるために押す必要があるスイッチの最小回数を求めるのがこの問題の目的です(同じスイッチは何度押しても構いません)。これは、配列内の右側のインデックスの値を反転させて、すべての値を1に設定する操作と同等です。

入力例

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

出力

最小右フリップ回数: 3

解説

初期状態は「1010」です。

2番目のスイッチを押す:- 1:101 反転回数=1
3番目のスイッチを押す:- 11:10 反転回数=2
4番目のスイッチを押す:- 111:1 反転回数=3

別の入力例

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

出力

最小右フリップ回数: 1

解説

初期状態 1000
2番目のスイッチを押す:- 1:111 反転回数=1

この1回の操作で、右側のすべての電球が点灯しました。

アルゴリズムの考え方

• 整数型の配列がN個の電球の状態を保持します。
• 関数minFlips(int arr[], int n)は、配列とその長さnを受け取り、配列のすべての値を1にする(消灯している電球をすべて点灯させる)ための最小の右フリップ回数を返します。
• 変数countはフリップの回数を記録するもので、初期値は0です。
• ブール変数flippedは、それまでに適用された反転の偶奇(現在のスイッチの実効状態)を追跡します。初期状態では何も反転していないためfalseです。
• i=0からn-1まで以下の処理を繰り返します。
  • 電球がONで、反転の影響もない場合(実効状態が1)は、何もしません。
  • 電球自体はOFFでも、すでに反転済みで実効的にONになっている場合も、何もしません。
  • 実効状態がOFF(0)の場合は、countを1増やし、以降のすべての電球に対する反転状態を切り替えます。
• ループが終了したら、countに格納された値を結果として返します。

C++コード例

// 配列のすべての値を1にするための最小右フリップ回数を求めるC++プログラム
#include <bits/stdc++.h>
using namespace std;

// 配列のすべての値を1にするために必要な最小の反転回数を計算する
int minFlips(int arr[], int n){
    int count = 0;
    bool flipped = false; // 初期状態ではまだ反転を行っていない
    for(int i = 0; i < n; i++){
        // これまでの反転を考慮した電球の実効状態
        int effective = arr[i] ^ (flipped ? 1 : 0);
        if(effective == 0){
            count++;            // 新たにスイッチを押す
            flipped = !flipped; // 右側全体の状態が反転する
        }
    }
    return count;
}
int main(){
    int Arr[] = {0, 1, 0, 1};
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << "配列のすべての値を1にする最小右フリップ回数: "
         << minFlips(Arr, N);
    return 0;
}

出力

配列のすべての値を1にする最小右フリップ回数: 4

計算量

時間計算量: O(n) ― 配列を一度だけ走査すればよいため非常に高速です。
空間計算量: O(1) ― 補助配列を使わず、定数個の変数だけで処理できます。

まとめ

この問題の鍵となるのは「プレフィックス反転」の考え方です。左から順に各電球を調べ、それまでに適用した反転回数の偶奇を記録しておけば、配列を実際に書き換えることなく、各要素を一度ずつ判定するだけでO(n)で答えを求められます。毎回右側を書き換える素朴なシミュレーションではO(n²)かかるところを、この最適化によって大幅に効率化できます。