C言語で解く変形ニムゲーム――最適な手で勝者を判定するアルゴリズム

変形ニムゲームとは？

変形ニムゲーム（Modified Game of Nim）は、配列を対象とした最適化ゲームの一種です。先攻プレイヤーの存在と、両者が取る最適な手に基づいて、最終的な勝者を予測します。

ゲームのロジック

このゲームでは、複数の要素を含む配列が与えられます。プレイヤー1（Player 1）とプレイヤー2（Player 2）の2人が対戦し、それぞれ自分が担当する数値を配列から取り除いていきます。具体的なルールは次のとおりです。

• プレイヤー1： 3で割り切れる数値をすべて取り除く
• プレイヤー2： 5で割り切れる数値をすべて取り除く

両プレイヤーが最適な戦略で要素を取り除いたとき、最終的にどちらが勝者となるかを求めるのがこの問題の狙いです。

サンプルケース

配列：{1, 5, 75, 2, 65, 7, 25, 6}
勝者：プレイヤーB
Aが75を除去 → Bが5を除去 → Aが6を除去 → Bが65を除去 → Aに打てる手がなくなり、Bの勝ち

解法のポイント

このプログラムでは、まず次の3つの値を数え上げます。

1. プレイヤー1のみが除去できる要素の数
2. プレイヤー2のみが除去できる要素の数
3. 両方のプレイヤーが除去できる要素の数（3と5の両方で割り切れる、すなわち15の倍数）

そのうえで、特に「両方が除去できる要素」の数に応じて勝敗を判定します。プレイヤー1は先手であるため、たとえ除去すべき要素が相手より1つ多くても勝利できます。通常の場合は、除去できる要素数が多いほうが勝者となります。

ニムゲームの勝者を求めるCプログラム

#include <bits/stdc++.h>
using namespace std;
int main() {
    int arr[] = {1,5, 75,2,65,7,25,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int movesA = 0, movesB = 0, movesBoth = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] % 3 == 0 && arr[i] % 5 == 0)
            movesBoth++;
        else if (arr[i] % 3 == 0)
            movesA++;
        else if (arr[i] % 5 == 0)
            movesB++;
    }
    if (movesBoth == 0) {
        if (movesA > movesB)
            cout<<"Player 1 is the Winner";
        cout<<"Player 2 is the Winner";
    }
    if (movesA + 1 > movesB)
        cout<<"Player 1 is the Winner";
    cout<<"Player 2 is the Winner";
    return 0;
}

出力結果

Player 2 is the Winner