C++で解くエリミネーションゲーム：最後に残る数を求めるアルゴリズム

問題の概要

1からnまでの整数が昇順に並んだリストを考えます。まず左から右へ向かって、先頭の数値とその後1つおきの数値を削除し、リストの末尾まで進みます。次に同じ操作を今度は右から左へ向かって行い、残った数値の中から右端の数値とその後1つおきの数値を削除します。この左右交互の削除操作を、数値が1つだけ残るまで繰り返します。長さnのリストから始めたとき、最後に残る数値を求めるのがこの問題です。

具体例：n = 9 の場合

入力が n = 9 のとき、削除の手順は以下のようになります（取り除かれる数値には下線を付けています）。

• 1, 2, 3, 4, 5, 6, 7, 8, 9

• 2, 4, 6, 8

• 2, 6

• 6

したがって、答えは 6 となります。

解法のアプローチ

毎回実際にリストを操作してシミュレーションすると非効率なため、ここでは状態をいくつかの変数だけで管理する効率的な手法を用います。ポイントとなる変数は以下の通りです。

• head：現時点で残っている数値のうち先頭（最小）の値

• step：現在のラウンドにおける隣接する残存要素同士の間隔

• rem：残っている要素数

• left：次の削除方向が左から右であることを示すフラグ

各ラウンドでは、削除方向が左から右の場合、または残り要素数が奇数の場合に、必ず先頭の要素が削除されます。そのため、これらの条件に該当するときは head を step 分だけ進めます。その後、step を2倍にし、方向フラグを反転させ、残り要素数を半分にします。この処理を rem が1になるまで繰り返し、最終的な head を答えとして返します。計算量は O(log n)、追加のメモリは O(1) で済むため、大きな n に対しても高速に動作します。

アルゴリズムの手順

• left := 1、head := 1、step := 1、rem := n で初期化する

• rem > 1 の間、以下を繰り返す

  • left が真、または rem が奇数の場合、head := head + step とする

  • step := step × 2 とする

  • left の真偽を反転させる

  • rem := rem / 2 とする

• head を返す

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int lastRemaining(int n) {
        int head = 1;
        int step = 1;
        int rem = n;
        int left = 1;
        while(rem > 1){
            if(left || rem % 2 == 1){
                head += step;
            }
            step *= 2;
            left = !left;
            rem /= 2;
        }
        return head;
    }
};
main(){
    Solution ob;
    cout << (ob.lastRemaining(9));
}

入力

9

出力

6