C++で0と1の配列を等しい値の3つの部分に分割する方法

問題概要

0と1だけで構成された配列Aが与えられます。この配列を、すべて同じ2進数値を表す3つの空でない部分に分割することを考えます。分割が可能な場合は、i+1 < j を満たす添字のペア [i, j] を返してください。分割は次のようになります。

• 第1部分：A[0], A[1], ..., A[i]
• 第2部分：A[i+1], A[i+2], ..., A[j-1]
• 第3部分：A[j], A[j+1], ..., A[A.length - 1]

3つの部分はそれぞれ等しい2進数値を持つ必要があります。条件を満たす分割が存在しない場合は [-1, -1] を返します。

たとえば、入力が [0,1,0,1,1] の場合、プログラムは [1, 4] を出力します。これは配列を「01」「01」「1」の3つの部分に分けると、いずれも2進数として1を表すためです。

アルゴリズムの手順

この問題は、末尾から決まる「第3部分」を基準に、先頭側・中間側がそれと一致するかを検証する方針で解きます。手順は以下の通りです。

補助関数 getIdx() の定義

引数として配列 a、left、right を受け取ります。

• left < right かつ a[left] が 0 である間、left を1ずつ増やします（先頭の余分な0を読み飛ばします）。
• right が配列のサイズに達するまで、a[left] と a[right] を順に比較します。一致しない場合は -1 を返します。
• 比較が完了したら left - 1 を返します（これが第1・第2部分の終端位置になります）。

メイン処理の流れ

• サイズ2の配列 ret を用意し、初期値を -1 で埋めます。
• num := 配列内の1の個数、n := 配列の長さ とします。
• num を3で割った余りが0でなければ、3等分は不可能なので ret を返します。
• num が 0 の場合（配列がすべて0の場合）、{ 0, 2 } を返します。
• req := num / 3 として、各部分に含まれるべき1の個数を求めます。
• 配列の末尾から req 個の1を数え、第3部分の開始位置 idx を特定して、idx を1つ進めます。
• firstEnd := getIdx(A, 0, idx)。結果が負なら分割不可として ret を返します。
• secondEnd := getIdx(A, firstEnd + 1, idx)。結果が負なら同様に ret を返します。
• { firstEnd, secondEnd + 1 } を返します。

C++実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> threeEqualParts(vector<int>& A){
       vector<int> ret(2, -1);
       int num = 0;
       int n = A.size();
       for (int i = 0; i < n; i++) {
          num += (A[i] == 1);
       }
       if (num % 3 != 0)
          return ret;
       if (num == 0) {
          return { 0, 2 };
       }
       int req = num / 3;
       int idx = n - 1;
       for (int temp = 0; idx >= 0 && temp < req; idx--) {
          temp += A[idx] == 1;
       }
       idx++;
       int firstEnd = getIdx(A, 0, idx);
       if (firstEnd < 0)
          return ret;
       int secondEnd = getIdx(A, firstEnd + 1, idx);
       if (secondEnd < 0)
          return ret;
       return { firstEnd, secondEnd + 1 };
    }
    int getIdx(vector<int>& a, int left, int right){
       while (left < right && a[left] == 0)
       left++;
       while (right < (int)a.size()) {
          if (a[left] != a[right])
             return -1;
          left++;
          right++;
       }
       return left - 1;
    }
};
main(){
    Solution ob;
    vector<int> v = {0,1,0,1,1};
    print_vector(ob.threeEqualParts(v));
}

入力と出力

入力：

{0,1,0,1,1}

出力：

[1, 4]

計算量のポイント

このアルゴリズムは配列を走査する回数が一定であるため、時間計算量は O(n)、追加の記憶領域は O(1) で済みます。そのため、大きな配列に対しても効率的に動作するのが特徴です。