C++で配列の全要素を0にするための最小操作回数を求める方法

問題の概要

サイズNの配列が与えられ、各要素は「1」または「0」のいずれかです。この課題では、すべての要素を0に変換するために必要な最小操作回数を求めます。

実行できる操作は以下のとおりです。

ある要素が「1」である場合、その値を「0」に変更できます。このとき、次のような効果が発生します。

• 隣接する次の要素が「1」であれば、その要素は自動的に「0」へ変換されます。
• 隣接する次の要素がすでに「0」であれば、何も起こりません。

例として、次の配列を考えてみましょう。

arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1}
この場合、すべての要素を0にするには 4回 の操作が必要です

アルゴリズム

1. 現在の要素が「1」であればカウントを1増やし、次に「0」が現れる位置まで探索を進めます。連続する「1」はすべて自動的に「0」へ変換されるため、まとめて処理できるからです。
2. 最終的なカウントを結果として返します。

C++による実装例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int performMinOperation(int *arr, int n){
   int i, cnt = 0;
   for (i = 0; i < n; ++i) {
      if (arr[i] == 1) {
         int j;
         for (j = i + 1; j < n; ++j) {
            if (arr[j] == 0) {
               break;
            }
         }
         i = j - 1;
         ++cnt;
      }
   }
   return cnt;
}
int main(){
   int arr[] = {1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1};
   cout << "Minimum required operations = " << performMinOperation(arr, SIZE(arr)) << endl;
   return 0;
}

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum required operations = 4

考え方のポイント

この問題の鍵となるのは、「連続する1のグループ数」を数えるという発想です。上記の例では、配列内に「1」が連続するブロックが {1, 1}、{1, 1, 1, 1, 1}、{1}、{1} の4つ存在します。各グループの先頭要素に対して一度だけ操作を行えば、残りの要素は連鎖的に自動的に0へ変換されます。したがって、必要な最小操作回数は「1」の連続グループの総数と一致します。

このアルゴリズムの計算量はO(N)であり、配列を一度走査するだけで答えが求まるため、非常に効率的です。