C++で解くズーマ（Zuma）ゲーム：全ボール消去に必要な最小挿入数を求めるアルゴリズム

ズーマゲームとは

ズーマ（Zuma）ゲームについて考えてみましょう。テーブルの上には一列にボールが並んでおり、それぞれのボールには赤（R）、黄（Y）、青（B）、緑（G）、白（W）のいずれかの色が付いています。また、こちらの手元にもいくつかのボールが用意されています。

各ターンでは、手元のボールを1つ選んで列の中に挿入できます。挿入後、同じ色のボールが3個以上連続して並んでいれば、そのグループは自動的に取り除かれます。この消去は連鎖的に発生し、これ以上ボールを取り除けなくなるまで繰り返されます。

この問題の目的は、テーブル上のボールをすべて消すために挿入する必要のあるボールの最小数を求めることです。すべてのボールを消すことが不可能な場合は、-1を返します。

具体例

入力が「WRRBBW」、手元のボールが「RBW」である場合、答えは3になります。手順は以下の通りです。

1. RRの後にRを挿入（WRR[R]BBW）→ 消去後の列は WBBW になる
2. 次にBを挿入（WBB[B]W）→ 消去後の列は WW になる
3. 最後にWを挿入（WW[W]）→ すべてのボールが消える

アルゴリズムの考え方

この問題は、深さ優先探索（DFS）による全探索で解くことができます。手順は以下の通りです。

• findMinStep(s, hand) を定義する。文字列sの末尾に番兵として「#」を連結し、サイズ26の配列vを用意して手元の各色のボール数をカウントします。その後、solve(s, v)を呼び出し、結果がINF以上なら-1を、そうでなければその値を返します。
• solve(s, v) を定義する。列が空（「#」のみ）であれば0を返します。2つのポインタiとjを使って同じ色の連続区間を走査し、そのグループを3個にするために必要なボール数 need = 3 - (j - i) を求めます。手元に十分なボールがあれば、need個を消費してグループを完成させ、残りの列に対して再帰的にsolveを呼び出し、retの最小値を更新します。
• 続いて process(s) を呼び出し、すでに3個以上連続している同色のグループを文字列から削除します。削除によって新たなグループが形成された場合も連鎖的に処理されます。
• その後、再度同じ走査を行い、最終的なretの値を返します。

実装例（C++）

以下にC++による実装を示します。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int findMinStep(string s, string hand) {
      s += "#";
      vector <int> v(26);
      for(int i = 0; i < hand.size(); i++){
         v[hand[i] - 'A']++;
      }
      int ret = solve(s, v);
      return ret >= INF ? -1 : ret;
   }
   int solve(string s, vector <int>& v){
      if(s == "#") return 0;
      int ret = INF;
      for(int i = 0, j = 0; j < s.size(); j++){
         if(s[i] == s[j]) continue;
         int need = 3 - (j - i);
         char x = s[i];
         if(need <= v[x - 'A']){
            v[x - 'A'] -= need;
            ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
            v[x - 'A'] += need;
         }
         i = j;
      }
      process(s);
      if(s == "#") return 0;
      for(int i = 0, j = 0; j < s.size(); j++){
         if(s[i] == s[j]) continue;
         int need = 3 - (j - i);
         char x = s[i];
         if(need <= v[x - 'A']){
            v[x - 'A'] -= need;
            ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
            v[x - 'A'] += need;
         }
         i = j;
      }
      return ret;
   }
   void process(string& s){
      for(int i = 0, j = 0; j < s.size(); j++){
         if(s[i] == s[j]) continue;
         if((j - i) >= 3){
            s.erase(i, j - i);
            j = i - 1;
         } else i = j;
      }
   }
};
main(){
   Solution ob;
   cout << (ob.findMinStep("WRRBBW", "RBW"));
}

入力

"WRRBBW", "RBW"

出力

3

計算量と実装のポイント

ボードの長さをn、手元のボール数をmとすると、挿入位置と使用するボールの組み合わせをすべて試すため、最悪の場合は指数オーダーの計算量になります。ただし、実際の制約（ボード長は16以下、手元のボールは5個以下など）では十分に高速に動作します。また、同じ状態（列の構成と手元のボール数）の再計算を避けるためにメモ化を導入すると、さらなる効率化が可能です。