【C++】全要素0の配列から目的の配列を構築するために必要な接尾辞インクリメント/デクリメント操作の回数を求める方法

問題概要

正の整数を含むターゲット配列 arr[] が与えられます。この記事のゴールは、すべての要素が 0 の初期配列から出発し、「接尾辞(サフィックス)インクリメント/デクリメント操作」だけを使って、このターゲット配列 arr[] を構築するために必要な操作の総回数を求めることです。

任意のインデックス i を選択した場合、各操作は次のように定義されます。

• 接尾辞インクリメント操作: インデックス i から配列の末尾までのすべての要素に 1 を加算する。
• 接尾辞デクリメント操作: インデックス i から配列の末尾までのすべての要素から 1 を減算する。

例1で理解する

入力 − arr[] = { 1, 2, 3 }

出力 − 必要な操作回数は 3

開始: { 0, 0, 0 }
インデックス 0 を選択し、接尾辞インクリメント適用 → { 1, 1, 1 }
インデックス 1 を選択し、接尾辞インクリメント適用 → { 1, 2, 2 }
インデックス 2 を選択し、接尾辞インクリメント適用 → { 1, 2, 3 }
合計操作回数 = 3

例2で理解する

入力 − arr[] = { 1, 4, 5, 3 }

出力 − 必要な操作回数は 7

開始: { 0, 0, 0, 0 }
インデックス 0 を選択し、接尾辞インクリメント適用 → { 1, 1, 1, 1 }
インデックス 1 を選択し、接尾辞インクリメント適用 → { 1, 2, 2, 2 }
インデックス 1 を選択し、接尾辞インクリメント適用 → { 1, 3, 3, 3 }
インデックス 1 を選択し、接尾辞インクリメント適用 → { 1, 4, 4, 4 }
インデックス 2 を選択し、接尾辞インクリメント適用 → { 1, 4, 5, 5 }
インデックス 3 を選択し、接尾辞デクリメント適用 → { 1, 4, 5, 4 }
インデックス 3 を選択し、接尾辞デクリメント適用 → { 1, 4, 5, 3 }
合計操作回数 = 7

解法のアプローチ

初期配列を B[] とします。このとき、以下のように考えることができます。

1. 最初の要素 B[0] を arr[0] に一致させるには、arr[0] 回の接尾辞インクリメント操作が必要です。この時点で B[0] = B[1] = … = B[n−1] = arr[0] となり、すべての要素が等しい状態になります。
2. 次に、B[1] を arr[1] に一致させるには、|arr[1] − arr[0]| 回の操作が必要です。値を増やしたい場合はインクリメントを、減らしたい場合はデクリメントを使用します。
3. 一般化すると、B[i] を arr[i] に一致させるには |arr[i] − arr[i−1]| 回の操作が必要になります。

したがって、必要な操作の総数は次の式で表せます。

|arr[0]| + |arr[1] − arr[0]| + … + |arr[n−1] − arr[n−2]|

アルゴリズムの手順

• ターゲット配列 arr[] を受け取ります。
• 関数 incr_decr_op(int arr[], int size) は、配列とその長さを受け取り、ターゲット配列を構築するために必要な接尾辞インクリメント/デクリメント操作の回数を返します。
• カウント変数 count を 0 で初期化します。
• for ループで配列 arr[] を走査します。
• 先頭の要素(i == 0)の場合は、count に abs(arr[i]) を加算します。
• それ以外のインデックスの場合は、count に abs(arr[i] − arr[i−1]) を加算します。
• ループが終了したら、count を結果として返します。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int incr_decr_op(int arr[], int size){
    int count = 0;
    for (int i = 0; i < size; i++){
        if (i > 0){
            count += abs(arr[i] - arr[i - 1]);
        }
        else{
            count = count + abs(arr[i]);
        }
    }
    return count;
}
int main(){
    int arr[] = { 3, 3, 1, 2, 2 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"指定された配列を構築するために必要な接尾辞インクリメント/デクリメント操作の回数: "<<incr_decr_op(arr, size) << endl;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

指定された配列を構築するために必要な接尾辞インクリメント/デクリメント操作の回数: 6

計算量

• 時間計算量: O(n) — 配列を一度だけ走査すればよいため。
• 空間計算量: O(1) — 追加の補助配列を一切必要としないため。

まとめ

この問題の鍵となるのは、隣接する要素間の差分に着目することです。接尾辞操作は「選択した位置以降のすべての要素に一様に影響する」ため、隣接要素の差の絶対値を順に累積していくだけで、最小の操作回数が求まります。配列全体を一度走査するだけで完了する、非常にシンプルかつ効率的な O(n) アルゴリズムです。