Powerset Construction DPについて

Posted on 4 mins read

AOJ 2587 Elevator Hall Numberを解いていて、オートマトンのPowerset Constructionに対応するDPをしていることに気づきました。
名前は適当にPowerset Construction DPとしておきます。

解説でもオートマトンを使った手法が書かれているのですが、DFAを明示的に構成しなくていいという点で異なるのでメモしておきます。

問題概要

下限$l_i$と上限$h_i$のペアが$n$個与えられる。
これらの条件を満たす自然数を$n$個左から順に並べたときにできる数が何種類あるか求めよ。
($2 \leq n \leq 6, 1 \leq l_i, r_i \leq 99$)

考察

$n$は小さいですが、できる数は最大12桁になるので愚直な全探索は間に合いません。

この問題を言い換えると、1桁の数字からなる文字列で、NFA(Non-deterministic Finite Automaton)が受理するものの種類を数え上げる問題になります。
例えば、$n = 2, l_0 = l_1 = 3, h_0 = h_1 = 45$のとき、以下のようなNFA(青が始状態、赤が受理状態)になります。

image_NFA

NFAについての詳しい説明は書きませんが、同じstateから同じ入力を受け取って複数の状態に行けるというのがポイントです。
このようにして作ったNFAは最大$11 \cdot n$個程度の状態数を持ってしまいますが、これは簡単にまとめることができます。

$ p_i: i-1個目のエレベーターをちょうど使い切り、次i個目のはじめから \\\ q_i: i個目の10の位最小の値を使った \\\ r_i: i個目の10の位間の値を使った \\\ s_i: i個目の10の位最大の値を使った $

というようにまとめると、最大$4 \cdot n$個程度の状態に減らすことができました。 先程の例の場合は下の図のようになります。

image_NFA_small

さて、受理する文字列の種類を数え上げたいのですが、重複無しで数え上げるのはなかなか難しいです。 これはオートマトンがNFAだからです。

実は任意のNFAは、Powerset Constructionという操作を行うことでDFA(Deterministic Finite Automaton)に変換することができます。
DFAに変換することで、現在のstateと入力が定まると行き先のstateが1つに定まるので、数え上げが非常に楽になります。
というわけで、今回の問題はPowerset Constructionを行ってDFAを構成することで解くことができます。

実は今回はさらに、DFAを明示的に構成する必要はありません。
Powerset Constructionでは、新たに元の集合の冪集合を集合として持つようなオートマトンを考え、達することのできる状態の集合に注目します。
競プロerの皆さんならこれに対応する概念を思いつくと思います。
そうです。bitDPです。

$ \mathrm{dp}[i][S]: i桁見たときに到達可能な状態集合がSであるような場合の数 $

として、もとのオートマトンを受理する文字列の種類数は、$S$が受理状態$p_n$を含むような場合の数の総和になります。

実装

$p_0, q_0, r_0, s_0, p_1, q_1, …$の順に$0, 1, 2, …$のindexを振っています。
配列だとメモリも実行時間も危なそうですが、実際は可能な状態がかなり少ないため unordered_map を使うと爆速で終わります。

#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve() {
  int n; cin >> n;
  if (n == 0) exit(0);
  vector<int> l(n), h(n);
  for (int i = 0; i < n; i++) cin >> l[i] >> h[i];

  vector<unordered_map<int, int>> dp(2);
  dp[0][1] = 1;
  int ans = 0;
  for (int i = 0; i < 2 * n + 1; i++) {
    for (const auto& p : dp[0]) {
      const int S = p.first;
      if (S >> (4 * n) & 1) ans += p.second;
      for (int x = 0; x < 10; x++) {
        int T = 0;
        for (int j = 0; j < 25; j++) {
          int k = j / 4;
          if ((S >> j & 1) == 0 || k >= n) continue;
          if (j % 4 == 0) {
            // k個目はじめから
            if (l[k] <= x && x <= h[k]) T |= 1 << (j + 4);
            if (x == 0) continue;
            if (l[k] / 10 == x) {
              T |= 1 << (j + 1);
            } else if (h[k] / 10 == x) {
              T |= 1 << (j + 3);
            } else if (l[k] / 10 < x && x < h[k] / 10) {
              T |= 1 << (j + 2);
            }
          } else if (j % 4 == 1) {
            // k個目10の位最小を使った
            int up = l[k] / 10 == h[k] / 10 ? h[k] % 10 : 9;
            if (l[k] % 10 <= x && x <= up) T |= 1 << (j + 3);
          } else if (j % 4 == 2) {
            // k個目10の位真ん中を使った
            T |= 1 << (j + 2);
          } else {
            // k個目10の位最大を使った
            if (x <= h[k] % 10) T |= 1 << (j + 1);
          }
        }
        dp[1][T] += p.second;
      }
    }
    swap(dp[0], dp[1]);
    dp[1].clear();
  }
  cout << ans << endl;
}
signed main() {
  while (1) solve();
}

終わりに

結構汎用的なテクニックだと思うんですが類題を知りません。
知ってる方がいたら教えてくださると助かります…