C++で実装するRLE（ランレングス符号化）イテレータ

ランレングス符号化（Run-Length Encoding）されたシーケンスを順に走査するイテレータの作成を考えてみましょう。イテレータは RLEIterator(int[] A) を呼び出すことで初期化されます。ここで A はシーケンスのランレングス符号化を表しており、すべての偶数インデックス i において、A[i] は非負の整数値 A[i+1] がシーケンス中に繰り返される回数を示します。このイテレータは次の1つの関数をサポートします。

• next(int n)：次の n 個の要素（n ≥ 1）を消費し、その中で最後に消費した要素を返します。消費できる要素がもう残っていない場合は、代わりに -1 を返します。

例として、A = [3,8,0,9,2,5] から始めてみましょう。これはシーケンス [8,8,8,5,5] をランレングス符号化したもので、「8が3個、9が0個、5が2個」と読み解けます。この A でイテレータを初期化した後、next(2)、next(1)、next(1)、next(2) の順に呼び出すと、最終的な結果は [8, 8, 5, -1] となります。

アルゴリズム

この問題は、以下の手順で解くことができます。

• コンストラクタで配列 A をコピーして保持し、インデックス idx を 0 で初期化します。
• next() メソッドは引数 n を受け取り、以下のように動作します。
• idx が配列サイズ未満かつ n > A[idx] の間、「n := n - A[idx]」として「idx := idx + 2」を繰り返します。
• idx が配列サイズ以上になった場合は -1 を返します。
• A[idx] := A[idx] - n と更新します。
• A[idx + 1] を返します。

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

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class RLEIterator {
    public:
    vector <int> A;
    int idx = 0;
    RLEIterator(vector<int>& A) {
        this->A = A;
        idx = 0;
    }
    int next(int n) {
        while(idx < A.size() && n > A[idx]){
            n -= A[idx];
            idx += 2;
        }
        if(idx >= A.size()) return -1;
        A[idx] = A[idx] - n;
        return A[idx + 1];
    }
};
main(){
    vector<int> v = {3,8,0,9,2,5};
    RLEIterator ob(v);
    cout << (ob.next(2)) << endl;
    cout << (ob.next(1)) << endl;
    cout << (ob.next(1)) << endl;
    cout << (ob.next(2)) << endl;
}

入力

[3,8,0,9,2,5] で初期化し、next(2)、next(1)、next(1)、next(2) を呼び出す

出力

8
8
5
-1

動作のポイント

このアルゴリズムの鍵となるのは、配列 A を直接書き換えながら残りの出現回数を管理している点です。next() が呼ばれるたびに、カウントを使い切ったペア（回数, 値）は idx を 2 ずつ進めることで一括してスキップされ、まだ余裕のあるペアは A[idx] から n を差し引くだけで処理できます。展開後のシーケンス長を N とすると、各要素は全体で一度しか消費されないため、一連の next() 呼び出し全体の計算量は O(N) に抑えられます。