C++でフリップゲームIIを解く：メモ化再帰による先手の必勝判定

問題概要

フリップゲームは、2人のプレイヤーが対戦するゲームです。「+」と「-」の2種類の文字のみからなる文字列が与えられ、プレイヤー1とプレイヤー2が交互に、連続する2文字の「++」を「--」へと反転していきます。自分の番に打てる手がなくなったプレイヤーが負けとなり、相手が勝者となります。

この記事では、先手のプレイヤーが必ず勝利できるかどうかを判定する関数を定義します。

例えば、入力が s = "++++" の場合、出力は true（1）になります。先手のプレイヤーは中央の「++」を反転して「+--+」という局面を作れば、その後どちらに相手が打っても必ず勝てるからです。

解法アプローチ

この問題はメモ化再帰（Memoization）を使うことで効率的に解けます。基本的な考え方は次の通りです。

• 現在の局面から取り得るすべての手を試す
• ある手を打った後、相手が負ける局面になれば、その手は勝ちにつながる
• 一度計算した局面の結果はマップに保存し、再計算を避ける

アルゴリズムの手順

1. メモ化用のマップ memo を定義する
2. 関数 solve() を定義する（引数は文字列 s）
3. s が memo に登録済みなら、memo[s] をそのまま返す
4. possible := false で初期化し、n を文字列の長さとする
5. i = 0 から n - 2 までループする：
   • s[i] と s[i + 1] がどちらも '+' の場合：
     • その2文字を '-' に変更して手を打つ
     • possible |= !solve(s) —— 相手側の結果が false なら自分の勝ち
     • 2文字を '+' に戻して局面を復元（バックトラック）
     • possible が true になった時点で、memo[s] に保存して即座に返す
6. ループ終了後も勝ち筋がなければ、memo[s] := possible（false）を返す
7. メイン処理からは solve(s) の結果を返す

C++での実装例

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    unordered_map <string, bool> memo;
    bool solve(string s){
        if (memo.count(s))
            return memo[s];
        bool possible = false;
        int n = s.size();
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == '+' && s[i + 1] == '+') {
                s[i] = '-';
                s[i + 1] = '-';
                possible |= !solve(s);
                s[i] = '+';
                s[i + 1] = '+';
                if (possible)
                    return memo[s] = possible;
            }
        }
        return memo[s] = possible;
    }
    bool canWin(string s) {
        return solve(s);
    }
};
main(){
    Solution ob;
    cout << (ob.canWin("++++"));
}

入力

"++++"

出力

1

計算量について

メモ化により、同じ局面を複数回評価することが避けられるため、探索空間が大幅に削減されます。ただし、局面の総数は文字列長に対して指数的に増える可能性があるため、非常に長い入力には注意が必要です。実務的には、短〜中程度の長さの文字列に対して十分高速に動作します。