C++で棒消しゲームの勝者を判定するプログラム

問題の概要

2つの整数 n と k が与えられます。Amal（アマル）と Bimal（ビマル）が次のようなシンプルなルールのゲームを行います。まず Amal が紙に n 本の棒を一列に並べて描きます。その後、プレイヤーは交互に、自分の番ごとに左端または右端からちょうど k 本の棒を消していきます。先手は Amal です。ある番の直前に紙上に残っている棒が k 本未満になった場合、その時点でゲームは終了します。Amal が Bimal よりも厳密に多くの手数を指せば Amal の勝ちとなり、勝者が誰になるかを求めるのがこの問題です。

例えば、入力が n = 10、k = 4 の場合、出力は「Bimal」になります。これは、Amal が 4 本の棒を消し、続いて Bimal が 4 本消した後、残りの棒は 2 本しかなく、Amal はこれ以上手を指せないためです。両者の手数が同じになるため、Amal は勝利条件を満たせません。

解法の考え方

この問題は、ゲーム全体で最大何手指せるかを考えることで非常にシンプルに解けます。1手につき必ず k 本の棒が消えるため、ゲーム全体の手数は floor(n / k)（n を k で割った商の小数点以下切り捨て値）になります。

• floor(n / k) が奇数の場合：最後の一手を Amal が指すことになり、Amal の手数が Bimal より 1 多くなる → 勝者は「Amal」
• floor(n / k) が偶数の場合：両者の手数が等しくなり、Amal はより多く手を指せない → 勝者は「Bimal」

もし (n / k) の商（小数点以下切り捨て）が奇数ならば:
    "Amal" を返す
それ以外は "Bimal" を返す

C++での実装例

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

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

string solve(int n, int k) {
    if ((n / k) % 2 != 0) {
        return "Amal";
    }
    return "Bimal";
}

int main() {
    int n = 10;
    int k = 4;
    cout << solve(n, k) << endl;
}

入力

10, 4

出力

Bimal

計算量について

このアルゴリズムは除算と剰余演算をそれぞれ1回行うだけで判定できるため、時間計算量は O(1) であり、追加のメモリもほとんど必要ありません。n や k がどれほど大きくなっても一定時間で答えを求められるのが大きな強みです。