C++で配列をすべて0に反転する最小操作回数を求めるアルゴリズム

問題の概要

0と1のみを含む整数配列 nums が与えられます。使用できる操作は次の1種類です。インデックス i を1つ選び、その位置の要素と、それより右側にあるすべての要素を反転する(0を1に、1を0に変更する)というものです。この操作を繰り返して、配列のすべての要素を0にするために必要な最小の操作回数を求めます。

具体例

例えば、入力が [1, 0, 1] の場合、出力は 3 になります。操作の流れは以下のとおりです。

• インデックス 0 に対して操作を実行 → 配列は [0, 1, 0] になる
• インデックス 1 に対して操作を実行 → 配列は [0, 0, 1] になる
• インデックス 2 に対して操作を実行 → 配列は [0, 0, 0] になり、完成

解法のアプローチ

この問題は、配列を左から右へ走査しながら、各位置がこれまでに何回反転されたかを追跡する貪欲法(グリーディ法)で効率的に解けます。手順は以下のとおりです。

• n を nums のサイズとします。
• サイズ n の配列 op を定義します(各位置での累積反転回数を記録)。
• 答えとなる ret を 0 で初期化します。
• i を 0 から配列の末尾まで順に処理します。
  • i - 1 >= 0 の場合、op[i] += op[i - 1] として累積反転回数を引き継ぎます。
  • (nums[i] + op[i]) & 1 が 0 以外(奇数)の場合、その位置の現在の値は 1 であることを意味するため、op[i] を 1 増やし(新しい操作を記録)、ret も 1 増やします。

なぜこの方法で最小回数になるのか

最も左にある「1」の位置より左で操作を行うと、その間にあるすべての 0 が 1 に変わってしまい、無駄が生じます。したがって、常に最も左の 1 の位置で操作を行うのが最適です。累積反転回数 op[i] を使えば、実際に配列を書き換えなくても各位置の現在の値を O(1) で判定できるため、全体を O(n) で処理できます。

C++での実装例

以下に、上記のアルゴリズムを実装したC++のコードを示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> op(n);
        int ret = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i - 1 >= 0) {
                op[i] += op[i - 1];
            }
            if ((nums[i] + op[i]) & 1) {
                op[i]++;
                ret++;
            }
        }
        return ret;
    }
};
main() {
    Solution ob;
    vector<int> v = {1,0,1};
    cout << (ob.solve(v));
}

入力

{1,0,1}

出力

3

計算量

• 時間計算量: O(n) — 配列を1回走査するだけです。
• 空間計算量: O(n) — 累積反転回数を記録する補助配列が必要です。