C++で解く！ボール除去ゲームの勝者を判定するプログラム

問題概要

4つの整数 n1、n2、k1、k2 が与えられます。ここに2つの箱があり、1つ目の箱には n1 個のボール、2つ目の箱には n2 個のボールが入っています。

Amal（アマル）と Bimal（ビマル）の2人がこのゲームをプレイします。Amal は自分の手番で1個から k1 個のボールを取り除くことができ、Bimal は1個から k2 個のボールを取り除くことができます。Amal が先手となり、2人は交互に手番を進めていきます。そして、自分の手番でボールを取り除けなくなったプレイヤーが負けとなります。このゲームの勝者が誰になるのかを求めるのが課題です。

具体例

例えば、入力が n1 = 2、n2 = 2、k1 = 1、k2 = 2 の場合を考えてみましょう。このときの出力は「Bimal」になります。どちらの箱にも2個ずつボールが入っている状態です。Amal が1つ目の箱から1個のボールを取り除くと、Bimal は2つ目の箱から1個または2個のボールを取ることができます。Amal がどのような手を選んでも、Bimal が最適な手を打ち続ければ必ず勝利できるのです。

解き方

この問題は、実はとてもシンプルに解くことができます。重要なポイントは、勝敗が k1 や k2 の値ではなく、n1 と n2 の大小関係だけで決まるという点です。各手番で必ず1個以上のボールを取り除けるため、ゲームは必ず有限回の手で終了します。n1 が n2 より大きい場合は Amal が、そうでない場合は Bimal が勝者となります。

したがって、次のようなロジックで答えを求められます。

if n1 > n2 then:
    return "Amal"
otherwise:
    return "Bimal"

C++による実装例

理解を深めるために、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;

string solve(int n1, int n2, int k1, int k2) {
    if (n1 > n2)
        return "Amal";
    else
        return "Bimal";
}
int main() {
    int n1 = 2;
    int n2 = 2;
    int k1 = 1;
    int k2 = 2;
    cout << solve(n1, n2, k1, k2) << endl;
}

入力

2, 2, 1, 2

出力

Bimal