C++で配列を復元する方法：区切りのない数字列から復元パターン数を求める

あるプログラムが配列 A の要素を出力することを考えてみましょう。しかし、このプログラムには小さなミスがあり、各要素の後に空白（スペース）が出力されていませんでした。そこで、出力された一つの文字列だけが残っている場合、元の配列を復元できるでしょうか？ここでは、配列の各要素は 1 以上 k 以下の範囲に含まれることが分かっているものとします。

つまり、文字列 s と整数 k が与えられたとき、元の配列を復元できる方法が何通りあるかを求めるのがこの問題です。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

例えば、入力が S = "1318"、k = 2000 の場合、出力は 8 になります。これは次の 8 通りの異なる配列を作れるためです。

[1318]、[131, 8]、[13, 18]、[1, 318]、[1, 3, 18]、[1, 31, 8]、[13, 1, 8]、[1, 3, 1, 8]

解法のアプローチ

この問題を解くために、以下の手順に従います。

• 定数 m = 10⁹ + 7 を定義します。
• メモ化用のマップ dp を定義します。
• 関数 add(a, b) を定義します。これは ((a mod m) + (b mod m)) mod m を返します。
• 再帰関数 help(idx, s, num, k) を定義します。
• idx が s のサイズ以上の場合は 1 を返します（文字列をすべて消費した＝復元成功）。
• dp に idx と num の組み合わせが既に存在する場合は、その計算済みの値 dp[idx][num] を返します。
• ret = 0 として初期化します。
• num が 1 以上かつ k 以下で、かつ s[idx] が '0' でない場合は、現在の num で区切りを入れられるため、add(help(idx, s, 0, k), ret) を計算します。
• num * 10 + (s[idx] - '0') が k 以下の場合は、さらに桁を伸ばせるため、add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k), ret) を計算します。
• 結果を dp[idx][num] に保存して返します。

一方、動的計画法（ボトムアップ）による解法では、main 部分で以下のように処理します。

• n := s のサイズとします。
• サイズ n + 1 の配列 ans を定義し、ans[0] = 1 と初期化します。
• s の先頭に空白を連結して、インデックスを 1 始まりに調整します。
• k を文字列 ks に変換しておきます。
• i を 1 から n までループさせます。
• 内側のループで j を i から逆方向にたどり、cnt が 10 以内である間、末尾から最大 10 桁までの部分文字列 temp を構築します。
• s[j] が '0' の場合は先頭ゼロになるためスキップします。
• temp のサイズが ks のサイズを超えたらループを抜けます。
• temp を数値 val に変換し、val が 1 以上 k 以下であれば、ans[i] += ans[j - 1] を加算します（mod m）。

最終的に ans[n] を返すことで、配列全体を復元する方法の総数が得られます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
   public:
   unordered_map<int, unordered_map<lli, int> > dp;
   lli add(lli a, lli b){
      return ((a % m) + (b % m)) % m;
   }
   int help(int idx, string& s, lli num, int k){
      if (idx >= s.size())
      return 1;
      if (dp.count(idx) && dp[idx].count(num))
      return dp[idx][num];
      int ret = 0;
      if (num >= 1 && num <= k && s[idx] != '0') {
         ret = add(help(idx, s, 0, k), ret);
      }
      if (num * 10 + (s[idx] - '0') <= k) {
         ret = add(help(idx + 1, s, num * 10 + (s[idx] - '0'), k),
         ret);
      }
      return dp[idx][num] = ret;
   }
   int numberOfArrays(string s, int k){
      int n = s.size();
      vector<lli> ans(n + 1);
      ans[0] = 1;
      s = " " + s;
      string ks = to_string(k);
      for (lli i = 1; i <= n; i++) {
         lli cnt = 1;
         string temp = "";
         for (lli j = i; j >= 1 && cnt <= 10; j--, cnt++) {
            temp = s[j] + temp;
            if (s[j] == '0')
               continue;
            if (temp.size() > ks.size())
            break;
            lli val = stol(temp);
            if (val >= 1 && val <= k) {
               ans[i] = add(ans[i], ans[j - 1]);
            }
         }
      }
      return ans[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numberOfArrays("1318",2000));
}

入力

"1318", 2000

出力

8

このように、メモ化再帰または動的計画法を用いることで、区切り情報を失った数字列から有効な配列の復元方法の数を効率的に求めることができます。先頭にゼロが来る分割や k を超える値への分割を除外しながら、各位置での復元パターン数を累積していくのがポイントです。