C++で与えられた文字から形成できる最大スコアの単語集合を求める方法

問題の概要

単語のリスト、使用できる1文字ずつの文字リスト、そして各文字ごとのスコアが与えられます。このとき、与えられた文字を使って作成できる有効な単語の集合の中から、合計スコアが最大になる組み合わせを見つける必要があります。

すべての文字を使い切る必要はなく、また各文字は1回しか使用できません。文字「a」「b」「c」…「z」のスコアは、それぞれ score[0]、score[1]、…、score[25] として与えられます。

たとえば、words = ["god", "good", "toc", "cat"]、letters = [a, g, o, o, d, d, d, c, t, t]、score = [5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0] という入力の場合、出力は 30 になります。この例では「good」（15点）と「cat」（15点）を選ぶことで、最大スコア 30 を達成できます。

解決のアプローチ

この問題は、各単語を「使う／使わない」の2択で再帰的に探索するバックトラッキングによって解くことができます。具体的な手順は以下の通りです。

• 2次元配列 dp を定義します。
• 関数 calc() を定義します。引数は文字列 s、マップ m、スコア配列 sc です。
  • ans := 0 で初期化します。
  • i := 0 から開始し、i が s のサイズ未満である間、i を1ずつ増やしながら以下を繰り返します。
    • x := s[i]
    • m[x] <= 0 の場合は 0 を返します（必要な文字がもう残っていないため）。
    • m[x] を1減らします。
    • ans := ans + sc[x - 'a']
  • 最後に ans を返します。
• 関数 solve() を定義します。引数はインデックス i、フラグ status、ペアの配列 v、マップ m、スコア配列 s です。
  • i が -1 の場合は 0 を返します。
  • x := v[i].second（単語そのもの）
  • ans := 0
  • status が 1 の場合は ans := calc(x, m, s)
  • ans > 0 かつ status が 1 の場合、j := 0 から x のサイズ未満まで j を1ずつ増やしながら m[x[j]] を1減らします（使用した文字を消費します）。
  • ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s)) を返します。
• メインメソッドでは以下を行います。
  • マップ m を定義し、letters の各文字の出現回数をカウントします。
  • ペアの配列 v を定義します。
  • words の各単語に対して calc() を呼び出し、作成可能な単語だけを { スコア, 単語 } のペアとして v に追加します。
  • 配列 v をソートします。
  • dp := サイズ (v のサイズ) × 2 の2次元配列を -1 で埋めて定義します。
  • max(solve(v のサイズ - 1, 0, v, m, s), solve(v のサイズ - 1, 1, v, m, s)) を返します。

動作のポイント

calc() は、単語を構成するのに必要な文字が手持ちに十分にあるかどうかを判定し、作成可能な場合はその単語のスコアを返します。一方、solve() は各単語について「選ぶ（status = 1）」と「選ばない（status = 0）」の2通りを試し、再帰的に最大値を求めます。これにより、各文字を1回しか使えないという制約を守りながら、最適な単語の組み合わせを探索できます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<vector<int> > dp;
   int calc(string s, map<char, int> m, vector<int>& sc){
      int ans = 0;
      for (int i = 0; i < s.size(); i++) {
         char x = s[i];
         if (m[x] <= 0)
            return 0;
         m[x]--;
         ans += sc[x - 'a'];
      }
      return ans;
   }
   int solve(int i, int status, vector<pair<int, string> > v,
   map<char, int> m, vector<int>& s){
      if (i == -1)
         return 0;
      string x = v[i].second;
      int ans = 0;
      if (status == 1)
         ans = calc(x, m, s);
      if (ans > 0 && status == 1) {
         for (int j = 0; j < x.size(); j++) {
            m[x[j]]--;
         }
      }
      return ans + max(solve(i - 1, 0, v, m, s), solve(i - 1, 1, v, m, s));
   }
   int maxScoreWords(vector<string>& w, vector<char>& l,
   vector<int>& s){
      int ans = 0;
      map<char, int> m;
      for (int i = 0; i < l.size(); i++)
         m[l[i]]++;
      vector<pair<int, string> > v;
      for (int i = 0; i < w.size(); i++) {
         string x = w[i];
         int flag = calc(x, m, s);
         if (flag) {
            v.push_back({ flag, x });
         }
      }
      sort(v.begin(), v.end());
      dp = vector<vector<int> >(v.size(), vector<int>(2, -1));
      return max(solve(v.size() - 1, 0, v, m, s), solve(v.size() -
      1, 1, v, m, s));
   }
};
main(){
   Solution ob;
   vector<string> words = {"god", "good", "toc", "cat"};
   vector<char> letters = {'a','g','o','o','d','d','d','c','t','t'};
   vector<int> score = {5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0};
   cout << (ob.maxScoreWords(words, letters, score));
}

入力

{"god", "good", "toc", "cat"},
{'a','g','o','o','d','d','d','c','t','t'},
{5,0,8,3,0,0,6,0,0,0,0,0,0,0,3,0,0,0,0,2,0,0,0,0,0,0}

出力

30