カードゲームの勝者を見つけるC++プログラム｜最大値比較で勝敗を判定する方法

n枚のカード（番号は1〜n）を使った面白いカードゲームを考えてみましょう。プレイヤーはAmalとBimalの2人で、それぞれk1枚・k2枚のカードを持っています。ゲームは次のように進みます。各ターンで、両者は手持ちの中から好きなカードを1枚選んでテーブルに出します。このとき相手にはどのカードを出したか分かりません。その後、2枚のカードが同時に公開され、より大きい数字のカードを出したプレイヤーが両方のカードを手に入れます。ここで重要なのは同じカードは何度でも使えるというルールです。配列AはAmalの持つカード、配列BはBimalの持つカードを表します。手持ちのカードが1枚もなくなったプレイヤーが負けとなり、最終的な勝者を求めるのがこの問題です。

たとえば、入力が n = 5、A = [3, 2]、B = [5, 1, 4] の場合、出力は「Bimal」になります。ゲームの流れを追うと、まず (3, 5) を出してBimalがすべてのカードを獲得し、次に (3, 1) ではAmalが2枚とも取り戻します。続いて (3, 4) では再びBimalが勝利し、最後にAmalが1を出すと、Bimalは5でそれを奪うため、Amalの手札は空になります。

解法のポイント

この問題を解く鍵は「カードは何度でも使える」というルールです。全体の中で最大の数字を持つプレイヤーは、そのカードを出し続けるだけで相手のどんなカードにも勝ち続けられる一方、最大値を持たない側はいずれ必ず負けます。そのため複雑なシミュレーションは不要で、Aの最大値とBの最大値を比較するだけで勝者が確定します。

• d（Aの最大値）が e（Bの最大値）より大きい場合 → 勝者は「Amal」
• それ以外の場合 → 勝者は「Bimal」

計算量は O(k1 + k2) で済むため、非常に効率的な解法です。

アルゴリズムの手順

以下の手順に従って解きます。

d := 0   // A の最大値
e := 0   // B の最大値
for initialize i := 0, when i < size of A, update (increase i by 1), do:
    f := A[i]
    if d < f, then:
        d := f
for initialize i := 0, when i < size of B, update (increase i by 1), do:
    f := B[i]
    if e < f, then:
        e := f
if d > e, then:
    return "Amal"
Otherwise
    return "Bimal"

C++での実装例

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

#include<bits/stdc++.h>
using namespace std;
string solve(int n, vector<int> A, vector<int> B){
    int d = 0;   // A の最大値
    int e = 0;   // B の最大値
    for(int i = 0; i < A.size(); i++){
        int f = A[i];
        if (d < f)
            d = f;
    }
    for(int i = 0; i < B.size(); i++){
        int f = B[i];
        if (e < f)
            e = f;
    }
    if (d > e)
        return "Amal";
    else
        return "Bimal";
}
int main(){
    int n = 5;
    vector<int> A = {3, 2};
    vector<int> B = {5, 1, 4};
    cout << solve(n, A, B) << endl;
}

入力

5, {3, 2}, {5, 1, 4}

出力

Bimal