C++で配列から最後に削除される要素の位置を求める方法

この記事では、サイズ N の整数型配列 arr[] と整数値 M が与えられたときに、配列から最後に削除される要素の位置を求めるアルゴリズムを解説します。

問題の概要

配列から要素を削除する際には、以下のルールに従って操作を行います。

• 配列内の各要素 arr[i] について、arr[i] > M の場合はその値をいったん取り出し、arr[i] − M を配列の末尾へ追加します。
• arr[i] ≤ M の場合は、その要素を配列から削除します。
• この操作を、配列が空になるまで繰り返します。

具体例で問題を理解する

入力：

arr[] = {5, 4, 8}, M = 3

出力：

3

解説：

操作に従って値を削除していくと、
{5, 4, 8} → {4, 8, 2} → {8, 1, 2} → {1, 2, 5} → {2, 5} → {5} → {2} → 空の配列
となり、最後に削除される値は 8 です。その位置は 3 番目です。

解法アプローチ

この問題には、「最後に削除される値は、ceil(arr[i] / M) の値が最大となる要素である」という性質を利用したシンプルな解法があります。

ceil(arr[i] / M) は、その要素が配列から消えるまでに何回の操作を受けるかを表す切り上げ除算です。したがって、配列を一度走査し、ceil(arr[i] / M) が最大となる位置を記録すれば、最後に削除される要素の位置が分かります。

なお、最大値を持つ要素が複数存在する場合は、配列の中でより後方に位置する要素が最後に削除されます。実装では配列を後ろから前に向かって走査し、現在の最大値より厳密に大きい値が出現したときだけ位置を更新することで、この条件を自然に満たしています。

C++での実装例

以下は、本解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
    for (int i = 0; i < n; i++) {
        arr[i] = (arr[i] / m + (arr[i] % m != 0));
    }
    int lastRemPos = -1, largestVal = -1;
    for (int i = n - 1; i >= 0; i--) {
        if (largestVal < arr[i]) {
            largestVal = arr[i];
            lastRemPos = i;
        }
    }
    return lastRemPos + 1;
}
int main(){
    int arr[] = {5, 4, 8, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 3;
    cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
    return 0;
}

実行結果

The position of last removed element in the array is 3

コードのポイント

• 最初のループでは、arr[i] / m + (arr[i] % m != 0) という式で切り上げ除算 ceil(arr[i] / m) を計算し、各要素を「削除までに必要な操作回数」に変換しています。
• 2番目のループでは、配列を末尾から先頭へ走査し、これまでの最大値を上回る値が見つかった場合にのみ位置を記録します。
• 計算量は時間 O(N)、追加メモリ O(1) と非常に効率的で、大きな配列でも高速に動作します。