C++で「100ゲーム」に勝てるか判定する方法｜ビットマスクDPによる先手必勝判定アルゴリズム

問題概要：「100ゲーム」とは

「100ゲーム」は、2人のプレイヤーが交互に1から10までの整数を1つずつ選び、現在の合計値に加算していくゲームです。最初に合計を100以上にしたプレイヤーの勝ちとなります。

ここでは、このゲームを少し変更したバージョンを考えます。プレイヤーは同じ整数を二度と使えないものとします。つまり、1〜15などの共通の数字プールから重複なしで数字を引き続け、合計が100以上に達した時点で勝敗が決まります。

具体的には、整数 maxChoosableInteger（選べる最大の数字）と desiredTotal（目標となる合計値）が与えられたとき、両者のプレイヤーが最善を尽くす前提で、先手のプレイヤーが強制的に勝利できるかどうかを判定します。

制約として、maxChoosableInteger は20以下、desiredTotal は300以下であると常に仮定できます。たとえば maxChoosableInteger = 20、desiredTotal = 11 の場合、結果は false になります。先手はどの数字を選んでも勝つことができないのです。

解法のアプローチ：ビットDPとメモ化再帰

この問題は、「どの数字が使用済みか」をビットマスクで管理し、メモ化再帰で解くのが定石です。手順は以下の通りです。

• サイズ 2²¹ の配列 dp を用意する
• n（最大の数字）、s（残りの目標値）、mask（使用済み数字の集合）を受け取るメソッド solve() を定義する
• s <= 0 の場合は false を返す（直前の手で相手が勝利したことを意味する）
• dp[mask] が -1 以外なら、その値を返す（メモ化済み）
• ret := false で初期化する
• i を 1 から n までループする
  • mask の i ビット目が 0（数字 i が未使用）の場合、ret := ret OR (NOT solve(n, s − i, mask XOR 2ⁱ)) とする
• dp[mask] := ret を保存して返す

さらに、メイン側では次のように処理します。

• desiredTotal <= 0 なら true を返す（初手で即勝利できるため）
• dp[0] から dp[2²¹−1] まですべて -1 で初期化する
• desiredTotal が 1〜n の総和 n×(n+1)/2 より大きければ false を返す（全部使っても目標に届かないため）
• solve(n, desiredTotal, 0) を返す

なぜ「相手の結果の反転」を取るのか

自分が数字 i を選んだ直後は相手の手番になります。solve() は「その状態で手番側が勝てるか」を返すため、自分が勝利するには「その状態で相手が負ける」ことが条件です。したがって、各選択肢について NOT solve(...) を計算し、OR で集約していくわけです。

C++での実装例

以下の実装を見ると、理解がより深まるでしょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int dp[1 << 21];
   bool solve(int n, int s, int mask){
      if(s <= 0) return false;
      if(dp[mask] != -1) return dp[mask];
      bool ret = false;
      for(int i = 1; i <= n; i++){
         if(!((mask >> i) & 1)){
            ret |= (!solve(n, s - i, (mask ^ (1 << i))));
         }
      }
      return dp[mask] = ret;
   }
   bool canIWin(int n, int desiredTotal) {
      if(desiredTotal <= 0) return true;
      for(int i = 0; i < (1 << 21); i++)dp[i] = -1;
      if(desiredTotal > (n * (n + 1)/ 2))return false;
      return solve(n, desiredTotal, 0);
   }
};
main() {
Solution ob;
cout << (ob.canIWin(10,11));
}

入力

10
11

出力

0

まとめ

maxChoosableInteger = 10、desiredTotal = 11 の場合、出力は 0（false）となり、先手はどのような手を選んでも勝利できないことがわかります。使用可能な数字の組み合わせは最大でも 2²⁰ 通りしか存在しないため、ビットマスクによるメモ化再帰を使えば、状態数を大幅に絞り込み、全探索を効率的に行えます。ゲーム理論的な勝敗判定が必要な場面で応用範囲の広いテクニックなので、ぜひマスターしておきましょう。