C++で解く：数値nから到達できる最小値を求めるゲーム問題

数値 n が与えられます。ゲーム開始時点での n の値は v であり、プレイヤーは次の操作を0回以上繰り返し実行できます。

操作： 正の整数 x(x < n かつ x が n の約数ではない)を選び、n から x を引く。

プレイヤーの目標は、最終的な n の値を最小化することです。

例えば、入力が n = 8 の場合、出力は 1 になります。最初の手番で x = 3 を選ぶと n は 5 になり、続いて x = 4 を選ぶことで n = 1 を達成できるためです。

解法の考え方

この問題は一見複雑に思えますが、実は非常にシンプルな規則性があります。

• n = 2 の場合： x < 2 を満たす正の整数は x = 1 のみですが、1 は 2 の約数であるため、操作を実行できません。よって答えは 2 となります。
• n ≥ 3 の場合： x = n − 1 を選べば必ず操作が可能です。n − 1 は n より小さく、n の約数にはなり得ない(n の約数で n/2 より大きいものは n 自身のみ)ためです。これにより n は 1 になります。

以上より、アルゴリズムは次のようにまとめられます。

if n が 2 と等しい場合:
    return 2
return 1

実装例

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

#include <bits/stdc++.h>
using namespace std;
int solve(int n){
    if (n == 2){
        return 2;
    }
    return 1;
}
int main(){
    int n = 8;
    cout << solve(n) << endl;
}

入力

8

出力

1

このように、約数の性質に着目することで、一見探索が必要な問題も O(1) の定数時間で解くことができます。