C++で1つおきの要素を削除した後、最後に残る要素を求めるアルゴリズム

問題の概要

1からnまでの整数が格納された循環配列を考えます。最初の要素から数え始め、2つおきに要素を削除していったとき、最後に残る要素を求めるのがこの問題です。例えば、入力が5の場合、配列は [1, 2, 3, 4, 5] となります。1から開始して2つおきに削除を進めると、配列の状態は以下のように変化します。

1 0 3 4 5
1 0 3 0 5
0 0 3 0 5
0 0 3 0 0

この結果、最後まで残る要素は 3 であることがわかります。

再帰を使った解法

この問題は、再帰的な漸化式を用いることで効率的に解くことができます。

まず、nが偶数の場合を考えてみましょう。1周目で 2, 4, 6, ... という偶数がすべて削除され、その後は再び 1 から数え始めます。つまり、n/2 個の要素が削除された後の状態は、「1, 3, 5, ... という奇数だけからなる長さ n/2 の配列で、1 から数え始める」状況とまったく同じです。新しい配列の i 番目の要素は元の配列の 2i−1 番目に対応するため、次の漸化式が成り立ちます。

一方、nが奇数の場合は、1周目で 2, 4, ..., n−1 が削除された後、さらに 1 が削除され、「3, 5, ..., n からなる長さ (n−1)/2 の配列で、3 から数え始める」状況になります。これらの性質から、以下の漸化式が導けます。

solve(n) = 2 * solve(n / 2) - 1        (n が偶数の場合)
solve(n) = 2 * solve((n - 1) / 2) + 1  (n が奇数の場合)

再帰の基本条件(ベースケース)は solve(1) = 1 です。

C++での実装例

#include <iostream>
using namespace std;

int deleteSecondElement(int n) {
    if (n == 1)
        return 1;
    if (n % 2 == 0)
        return 2 * deleteSecondElement(n / 2) - 1;
    else
        return 2 * deleteSecondElement((n - 1) / 2) + 1;
}

int main() {
    int n = 5;
    cout << "Remaining Element: " << deleteSecondElement(n) << endl;

    n = 10;
    cout << "Remaining Element: " << deleteSecondElement(n) << endl;

    return 0;
}

実行結果

Remaining Element: 3
Remaining Element: 5

計算量

このアルゴリズムは、再帰呼び出しのたびに問題のサイズが半分になるため、時間計算量は O(log n) です。また、再帰スタックの深さも O(log n) であるため、空間計算量も O(log n) となります。