要素の値がインデックスを超える場合に必要な最小操作回数を求めるC++プログラム

問題概要

n個の要素からなる配列Aがあるとします。この配列に対して、次の操作を何度でも実行できます。

• 任意の正整数kを選ぶ
• 数列の中から任意の位置を選び、その位置にkを挿入する
• 数列が更新されるため、以降の操作は新しい数列に対して行う

このとき、すべてのインデックスi(0以上n-1以下)について「A[i] <= i」という条件を満たすために必要な最小操作回数を求めるのが目的です。

例えば、入力が A = [1, 2, 5, 7, 4] の場合、出力は3になります。実際、次のような手順で操作を行うことで条件を満たせます。

[1,2,5,7,4] → [1,2,3,5,7,4] → [1,2,3,4,5,7,4] → [1,2,3,4,5,3,7,4]

解法の考え方

この問題は、各要素に着目して「あといくつ要素を挿入すれば条件を満たせるか」を考えることで解けます。

インデックスiにある要素A[i]が条件A[i] <= iを満たしていない場合、その手前に適切な正整数を挿入して位置を後ろにずらす必要があります。このとき必要な挿入回数は「A[i] - i - 1」です。挿入する値自身も条件を満たすように自由に選べるため、答えはすべてのiにおける「A[i] - i - 1」の最大値になります。

アルゴリズムの手順

1. 変数maxjを0で初期化する
2. nを配列Aのサイズとする
3. iを0からn-1まで走査し、maxjをmax(maxj, A[i] - i - 1)で更新する
4. maxjを返す

maxj := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    maxj := maximum of maxj and (A[i] - i - 1)
return maxj

C++による実装例

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
    int maxj = 0;
    int n = A.size();
    for (int i = 0; i < n; i++) {
        maxj = max(maxj, A[i] - i - 1);
    }
    return maxj;
}
int main() {
    vector<int> A = { 1, 2, 5, 7, 4 };
    cout << solve(A) << endl;
}

入力例

{ 1, 2, 5, 7, 4 }

出力例

3

計算量

このアルゴリズムの時間計算量はO(n)、空間計算量はO(1)です。配列を一度走査するだけで答えが求まるため、非常に効率的な解法となっています。