C++で解くニムゲーム：先手の勝敗を判定するシンプルなアルゴリズム

ニムゲームとは

ニムゲームは、2人のプレイヤーが交互に石を取り合う古典的なゲームです。山になっている石から、各ターンで1個から3個の石を取り除くことができ、最後の石を取ったプレイヤーが勝者となります。ここでは、プレイヤー1が先手として最初に石を取るものとします。また、両プレイヤーとも非常に賢く、常に最適な戦略を取ると仮定します。与えられた石の総数をもとに、プレイヤー1が勝利できるかどうかを判定するアルゴリズムを考案しましょう。

例えば、入力が5の場合、出力はtrue（真）になります。石が5個あるとき、プレイヤー1が最初に1個取れば4個残ります。次にプレイヤー2が何個取ろうと（1〜3個）、その後に必ず1〜3個の石が残るため、プレイヤー1が残りをすべて取って勝利できるのです。

解法のアプローチ

この問題は、実はたった一つのシンプルな条件で解くことができます。

• n を 4 で割った余りが 0 でなければ true を返し、0 であれば false を返す

なぜ「4」が鍵となるのでしょうか。各ターンで最大3個までしか石を取れないため、相手に「4の倍数」の状態を渡してしまえば、相手が何個取っても自分が調整して再び4の倍数に戻すことができます。つまり、先手が勝つには、初手で残りの石の数を4の倍数にすればよいのです。逆に、最初から石の数が4の倍数である場合、この戦略を後手側が使えるため、先手は必ず負けます。

実装例

以下のC++コードで、実際の動作を確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool canWinNim(int n) {
        return n%4!=0;
    }
};
main(){
    Solution ob;
    cout << (ob.canWinNim(5));
}

入力

5

出力

1

計算量について

この解法は剰余演算を1回行うだけなので、時間計算量・空間計算量はいずれも O(1) です。石の数がどれだけ大きくなっても一定時間で答えを求められる、非常に効率的なアルゴリズムと言えます。