C++でゴーストゲームの先手プレイヤーが勝利できるかを判定するプログラム

単語のリストが与えられているとします。ここで、2人のプレイヤーが参加する「ゴーストゲーム」について考えてみましょう。このゲームでは、プレイヤーが交互に文字列へ文字を追加していきます。作成中の文字列は、常にリスト内のいずれかの単語の有効な接頭辞(プレフィックス)でなければならず、リスト内の単語を完成させてしまったプレイヤーが負けとなります。両者のプレイヤーが最適な戦略を取る場合、先手のプレイヤーが勝つことができるかどうかを判定する必要があります。

例えば、入力が words = ["manage", "manager", "min"] の場合、出力は True になります。以下のように進めることができるためです。

• m [プレイヤー1]
• ma [プレイヤー2]
• man [プレイヤー1]
• mana [プレイヤー2]
• manag [プレイヤー1]
• manage [プレイヤー2] 負け

したがって、この場合はプレイヤー1の勝ちとなります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• マップ mp を1つ定義します
• words 内の各単語 it に対して、次の処理を行います
  • ch := it[0](単語の先頭文字)
  • it を mp[ch] に挿入します
• mn := 無限大(inf)で初期化します
• mp 内の各キーと値のペア it に対して、次の処理を行います
  • str := 値(そのグループ内の最小の文字列)
  • size := str のサイズ
  • size を 2 で割った余りが 0 の場合(偶数の場合)、1 を返します
• どのグループも該当しなければ 0 を返します

ポイントは、単語の長さが偶数であれば、その単語を完成させる最後の文字は偶数番目の手、すなわち後攻プレイヤーの番で置かれるという点です。これにより、先手は戦略的に有利な立ち回りが可能になります。

実装例(C++)

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

#include <bits/stdc++.h>
using namespace std;
bool solve(vector<string> &words) {
    map<char, set<string>> mp;
    for (auto &it : words) {
        char ch = it[0];
        mp[ch].insert(it);
    }
    int mn = INT_MAX;
    for (auto &it : mp) {
        string str = *(it.second.begin());
        int size = str.size();
        if (size % 2 == 0)
            return 1;
    }
    return 0;
}
int main(){
    vector<string> v = {"manage", "manager", "min"};
    cout << solve(v);
}

入力

{"manage", "manager", "min"}

出力

1