C++でステッカーを使って目標の単語を綴る：必要な最小枚数を求めるビットDP解法

問題概要

N種類の異なるステッカーがあるとしましょう。それぞれのステッカーには、小文字の英単語が1つ印刷されています。このステッカーのコレクションから個々の文字を切り取り、並べ替えることで、与えられたターゲット文字列を綴りたいと考えています。同じ種類のステッカーは必要に応じて何度でも使用でき、各ステッカーは無限枚用意されているものとします。

求めるのは、ターゲットを綴るために必要な最小のステッカー枚数です。もしターゲットを綴ることが不可能な場合は、-1を返してください。

たとえば、入力が ["dog", "sentence", "antenna"] で、ターゲットが "dance" の場合、答えは 3 になります。

解法の考え方：ビットマスクDP

この問題は、ビットマスクを用いた動的計画法(DP)によって効率的に解くことができます。

基本となるアイデアは次のとおりです。ターゲット文字列の各文字の位置をビットに対応させ、「その位置の文字がすでに埋まっているかどうか」を整数のビットフラグで表現します。たとえばターゲットが5文字なら、取りうる状態は 2^5 = 32 通りです。

dp[mask] を「mask で表される位置の文字がすべて埋まっている状態に到達するまでに必要な最小ステッカー枚数」と定義します。各状態から手持ちの各ステッカーを1枚使って遷移できる次の状態を試し、全文字が埋まった状態 dp[N-1] への最小コストを探索していきます。

アルゴリズムの手順

• n := ターゲットの長さ
• N := 1 を n 回左シフトした値(= 2^n)
• サイズ N の配列 dp を定義し、すべての要素を無限大(INT_MAX)で初期化する
• dp[0] := 0(まだ何も埋まっていない状態は0枚)
• i を 0 から N 未満まで1ずつ増やしながらループ:
  
  • dp[i] が INT_MAX と等しい場合は、到達不能な状態なので次の反復へスキップする
  • j を 0 からステッカーの総数未満まで1ずつ増やしながらループ:
    
    • s := stickers[j]
    • x := i(現在のマスクをコピー)
    • k を 0 から s の長さ未満までループ:
      
      • z := s[k](ステッカーの各文字)
      • l を 0 からターゲットの長さ未満までループ:
        
        • target[l] が z と一致し、かつ ((x を l ビット右シフト) AND 1) が 0(まだ埋まっていない)の場合:
          
          • x := x OR (1 を l ビット左シフト)してビットを立てる
          • 内側のループを抜ける
    • dp[x] := min(dp[x], dp[i] + 1)

ループ終了後、dp[N-1](全文字が埋まった状態)が INT_MAX のままなら -1 を返し、それ以外の場合は dp[N-1] の値を返します。

C++による実装

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minStickers(vector<string>& stickers, string target) {
        int n = target.size();
        int N = 1 << n;
        vector <int> dp(N, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < N; i++){
            if(dp[i] == INT_MAX) continue;
            for(int j = 0; j < stickers.size(); j++){
                string s = stickers[j];
                int x = i;
                for(int k = 0; k < s.size(); k++){
                    char z = s[k];
                    for(int l = 0; l < target.size(); l++){
                        if(target[l] == z && ((x >> l) & 1) == 0){
                            x |= (1 << l);
                            break;
                        }
                    }
                }
                dp[x] = min(dp[x], dp[i] + 1);
            }
        }
        return dp[N - 1] == INT_MAX? -1 : dp[N - 1];
    }
};
main(){
    Solution ob;
    vector<string> v = {"dog", "sentence","antenna"};
    cout << (ob.minStickers(v, "dance"));
}

入力

["dog", "sentence","antenna"]
"dance"

出力

3

コードのポイントと計算量

• 状態管理： 整数 i の各ビットが「ターゲットの対応する位置が埋まったかどうか」を表します。(x >> l) & 1 で状態を確認し、x |= (1 << l) でビットを立てます。
• 1文字につき1か所のみ: ステッカー上の1つの文字は、ターゲット内の同じ文字のうち「まだ埋まっていない最初の1か所」しか埋められないため、内側のループで break しています。これにより、1枚のステッカーの各文字インスタンスが正しく扱われます。
• 時間計算量： 状態数は 2^n(n はターゲットの長さ)、各状態ごとに全ステッカー(S 種類)・ステッカーの文字数(L)・ターゲット長(n)を走査するため、全体で O(2^n × S × L × n) となります。競技プログラミングで一般的な n ≤ 15 程度の制約であれば十分高速に動作します。

貪欲に文字数の多いステッカーを選ぶ方針では最適解を保証できませんが、ビットDPを活用することで、この問題を確実に最適解へ導くことができます。