C++で最後に残るモンスターの最小体力を求める方法(GCDの活用)

問題概要

N体のモンスターが存在し、各モンスターは整数の初期体力 h[i] を持っています。体力が0より大きいモンスターは「生存している」とみなされます。

各ターンでは、ランダムに選ばれたモンスターが別のランダムなモンスターを攻撃します。攻撃を受けたモンスターの体力は、攻撃した側のモンスターの体力と同じ値だけ減少します。このプロセスは、モンスターが1体だけ残るまで繰り返されます。このとき、最後に残ったモンスターの体力として考えられる最小値を求めてください。

具体例

入力配列が {2, 14, 28, 56} の場合、出力は 2 になります。これは、体力2のモンスターが残りの3体を攻撃し続けたとき、最後に残るモンスターの体力が2となり、これが最小値だからです。

アルゴリズム:最大公約数(GCD)を使う

この問題の答えは、すべてのモンスターの体力の最大公約数(GCD)と一致します。次の式で表せます。

H(min) = gcd(h1, h2, ..., hn)

なぜGCDで求まるのか

攻撃による体力の減少は「ある値から別の値を引く」という操作であり、これはユークリッドの互除法(減算によるGCD計算)とまったく同じ構造です。減算操作を行っても数列全体の最大公約数は不変であるため、最後に残る体力は必ず初期値全体のGCDになります。さらに、攻撃の順序を工夫することでGCDそのものの値を最終体力として実現できるため、これが最小値となります。

C++による実装例

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (a == 0)
    return b;
    return gcd(b % a, a);
}
int getPossibleHealth(int* health, int n) {
    int currentGcd = gcd(health[0], health[1]);
    for (int i = 2; i < n; ++i) {
        currentGcd = gcd(currentGcd, health[i]);
    }
    return currentGcd;
}
int main() {
    int health[] = { 4, 6, 8, 12 };
    int n = sizeof(health) / sizeof(health[0]);
    cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Possible final health = 2

計算量

モンスターがN体の場合、GCDの計算をN-1回繰り返すことになります。ユークリッドの互除法は対数時間で動作するため、全体の計算量は O(N log max(h)) となり、非常に効率的な解法です。