C++で解く「奇妙なプリンター」問題 ― 区間DPで最小ターン数を求める

奇妙なプリンター問題とは

「奇妙なプリンター(Strange Printer)」は、次のような制約を持つ架空の印刷装置に関する問題です。

• 1回の操作で印刷できるのは、同じ文字が連続した列のみである。
• 各ターンでは、好きな開始位置から好きな終了位置まで新しい文字を印刷でき、すでに印刷済みの文字は上書きされる。

小文字アルファベットのみで構成された文字列が与えられたとき、この文字列を完成させるまでに必要な最小ターン数を求めるのが課題となります。

たとえば入力が「aaabba」の場合、答えは2ターンです。まず「aaaaaa」と全体をaで印刷し(1ターン目)、続いて該当する位置をbで上書きすれば(2ターン目)、目的の文字列が得られます。

解法のアプローチ:区間DP

この問題は区間動的計画法(区間DP)を用いることで効率的に解けます。dp[i][j]を「部分文字列s[i..j]を印刷するのに必要な最小ターン数」と定義し、以下の手順で計算していきます。

1. nを文字列sの長さとします。
2. nが0の場合は0を返します。
3. n×nの2次元配列dpを用意し、すべて無限大(INF)で初期化します。
4. 部分文字列の長さlを1からnまで伸ばしながら処理します。
   • i=0、j=l−1とし、jがn未満の間、iとjを1ずつ増やしながら以下を実行します。
     • l==1のとき:dp[i][j]=1(1文字は1ターンで印刷可能)
     • l==2のとき:s[i]とs[j]が等しければdp[i][j]=1、異なれば2
     • それ以外のとき:分割位置k(i ≤ k < j)を全探索します。
       • temp=dp[i][k]+dp[k+1][j]を計算します。
       • s[k]とs[j]が等しい場合はtemp−1、そうでなければtempとし、現在のdp[i][j]より小さければ値を更新します。両端の文字が一致する場合、1回の印刷で両側をまとめて処理できるため、ターン数を1削減できるのがポイントです。
5. 最終的にdp[0][n−1]を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector<vector<int>> dp(n, vector<int>(n, INF));
      for(int l = 1; l <= n; l++){
         for(int i = 0, j = l - 1; j < n; i++, j++){
            if(l == 1){
               dp[i][j] = 1;
            } else if(l == 2){
               dp[i][j] = (s[i] == s[j]) ? 1 : 2;
            } else {
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], (s[k] == s[j]) ? temp - 1 : temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};

int main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

入力例

"aaabba"

出力例

2

計算量の目安

各区間について分割位置kを全探索するため、時間計算量はO(n³)となります。また、2次元のDPテーブルを保持するため、空間計算量はO(n²)です。なお、事前に連続する重複文字を圧縮してからDPを行うことで、実際の計算コストをさらに抑えることもできます。