C++で数字を選択し、合計の絶対差に基づいてゲームの勝者を予測する方法

この問題では、n個の整数からなる配列が与えられ、プレイヤーXとプレイヤーYの2人がその数字を使ってゲームを行います。私たちのタスクは、どちらのプレイヤーが勝つかを事前に予測することです。

勝敗を決めるルールはシンプルです。プレイヤーXが選んだ数字の合計と、プレイヤーYが選んだ数字の合計の絶対差が4の倍数であればXの勝ち、4で割り切れない場合はYの勝ちとなります。なお、ゲームは必ずプレイヤーXから開始されます。

問題の具体例

まず、入力例と出力例を見ながら問題を理解しましょう。

入力：a[] = {3, 6, 9, 12}
出力：X

解説：
Xは 3 と 6 を選択（合計 9）
Yは 12 と 9 を選択（合計 21）
|9 − 21| = 12 → 12は4の倍数なのでXの勝ち

解法のアプローチ

この問題を効率的に解く鍵は、「各要素を4で割った余り」に注目することです。

配列のすべての要素について、4で割った余り（0〜3）の出現回数をカウントします。もしすべての余りの出現回数が偶数であれば、両者の合計の絶対差は必ず4の倍数になり、Xの勝利が確定します。逆に、どれか一つでも奇数の余りが存在すれば、Yの勝ちとなります。

言い換えると、arr[i] % 4 の値が 0、1、2、3 のそれぞれについて出現回数が偶数であるかどうかを確認すればよいのです。

アルゴリズムの手順

1. 大きさ4のカウント配列を用意し、すべて0で初期化する。
2. 配列の各要素について、4で割った余りを求め、対応するカウントを1増やす。
3. カウント0〜3がすべて偶数であれば1（Xの勝ち）を返し、そうでなければ2（Yの勝ち）を返す。

C++での実装例

#include <iostream>
using namespace std;

int playGame(int a[], int n) {
    int count[4] = {0, 0, 0, 0};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 4; j++) {
            if (a[i] % 4 == j)
                count[j]++;
        }
    }
    if (count[0] % 2 == 0 && count[1] % 2 == 0 && count[2] % 2 == 0 && count[3] % 2 == 0)
        return 1;
    else
        return 2;
}

int main() {
    int a[] = { 4, 8, 5, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Game Started!\n";
    if (playGame(a, n) == 1)
        cout << "X wins the Game";
    else
        cout << "Y wins the Game";
    return 0;
}

実行結果

Game Started!
X wins the Game

コードの解説

上記の例では、配列 {4, 8, 5, 9} の各要素を4で割ると、余りは順に 0、0、1、1 となります。余り0が2回、余り1が2回出現しており、すべて偶数であるため、関数 playGame は1を返し、「X wins the Game」と表示されます。

このアルゴリズムは配列を一度走査するだけなので、時間計算量は O(n)、追加で必要なメモリは固定サイズのカウント配列のみで O(1) です。大規模な入力にも対応できる、非常に効率的な解法と言えます。