最小・最大除去ゲームで最後に残る数を求めるC++コードの解説

問題概要

n個の要素からなる配列Aがあり、ボード上にn個の数値が書かれているとします。AmalとBimalが交互にターン制のゲームを行います。各ターンで、プレイヤーは数値を1つ選んでボードから取り除きます。Amalが先手です。Amalは最後にボードへ残る数をできるだけ小さくしたいと考え、一方のBimalはそれをできるだけ大きくしたいと考えています。このとき、最終的にボードに残る数を求めましょう。

例えば、入力が A = [2, 1, 3] の場合、出力は 2 になります。これは、Amalが先に 3 を取り除き、次にBimalが 1 を取り除くため、最後に残る数が 2 になるからです。

解法のアプローチ

この問題を解くためには、以下の手順に従います。

• n を配列 A のサイズとします。
• 配列 A を昇順にソートします。
• A[(n − 1) / 2](切り捨て除算)を返します。

なぜ中央値が答えになるのか

両者が最適な戦略を取るとき、最後に残る数は配列の中央値になります。ソート後の配列では、Amalは大きい側の要素から順に取り除こうとし、Bimalは小さい側の要素から順に取り除こうとします。両者の行動が互いに打ち消し合う結果、ちょうど中央の位置にある要素が最後まで残るのです。

C++での実装例

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

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

int solve(vector<int> A){
    int n = A.size();
    sort(A.begin(), A.end());
    return A[(n - 1) / 2];
}

int main(){
    vector<int> A = { 2, 1, 3 };
    cout << solve(A) << endl;
}

入力

{ 2, 1, 3 }

出力

2

計算量

このアルゴリズムの時間計算量は O(n log n)(ソートにかかるコスト)、空間計算量は O(1) となります。非常にシンプルでありながら、ゲーム理論におけるミニマックス戦略の性質を利用した効率的な解法です。