AOJ 2587 - Elevator Hall Number

競プロ AOJ

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2587

解法

桁DPしようと思ったが、遷移がうまく書けないので困った。
そこでオートマトンをイメージする。
結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。
オートマトンとして考えるべき状態は、以下の4つがある。

  • P[i] := i 番目のエレベーターまで完了直後
  • Q[i] := i+1 番目のエレベーターの途中で、low の2桁目の値
  • R[i] := i+1 番目のエレベーターの途中で、low と high の2桁目の間の値
  • S[i] := i+1 番目のエレベーターの途中で、high の2桁目の値

low, high の値に応じて、P[i] -> Q[i], Q[i] -> P[i + 1], ... などの遷移を書く。
すると、NFA のノードの数は 4 * n + 1 個になる。
したがって、NFA のノードには P[i] = 4 * i, Q[i] = 4 * i + 1, ... と番号を振っておくと、DFA を作るときに bit で管理できる。
DFA の構築は普通に初期状態 P[0] から BFS して、各ノードに対し、遷移先の ID の集合をbitで管理すればOK。

DFA ができたらあとは普通の DP で、メモ化再帰でやるとすれば 終了状態 P[n] の時 1 であり、それ以外のときは遷移先をすべて足し合わせた値になる。
ただし、現状態が終了状態を含む場合（普通にありえます）は、この値に +1 する必要がある。

計算量は O(4^N * 10) 程度でおもそうだが、DFA の探索空間はたいしたことないから問題なし。

ソースコード

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

using ll = long long;

int main() {
    int n;
    while(cin >> n, n) {
        vector<int> low(n), high(n);
        for(int i = 0; i < n; ++i) {
            cin >> low[i] >> high[i];
        }

        // build NFA
        const int fin = n * 4; // finish node
        vector<vector<vector<int>>> nfa(n * 4 + 1, vector<vector<int>>(10));
        for(int i = 0; i < n; ++i) {
            if(low[i] < 10) { // Pi -> Pi+1
                for(int x = low[i]; x <= min(9, high[i]); ++x) {
                    nfa[i * 4][x].push_back(i * 4 + 4);
                }
            } else {
                // Pi -> Qi -> Pi+1
                nfa[i * 4][low[i] / 10].push_back(i * 4 + 1);
                const int ub = low[i] / 10 == high[i] / 10 ? high[i] % 10 : 9;
                for(int x = low[i] % 10; x <= ub; ++x) {
                    nfa[i * 4 + 1][x].push_back(i * 4 + 4);
                }
            }
            // Pi -> Ri -> Pi+1
            for(int x = low[i] / 10 + 1; x < high[i] / 10; ++ x) {
                nfa[i * 4][x].push_back(i * 4 + 2);
            }
            for(int x = 0; x <= 9; ++x) {
                nfa[i * 4 + 2][x].push_back(i * 4 + 4);
            }
            if(high[i] >= 10) {// Pi -> Si -> Pi+1
                nfa[i * 4][high[i] / 10].push_back(i * 4 + 3);
                const int lb = low[i] / 10 == high[i] / 10 ? low[i] % 10 : 0;
                for(int x = lb; x <= high[i] % 10; ++x) {
                    nfa[i * 4 + 3][x].push_back(i * 4 + 4);
                }
            }
        }

        // build DFA
        map<int, array<int, 10>> dfa;
        {
            queue<int> que;
            que.push(1);
            set<int> vis = {1};
            while(!que.empty()) {
                const int S = que.front();
                que.pop();
                for(int x = 0; x <= 9; ++x) {
                    int nS = 0;
                    for(int i = 0; i < 4 * n; ++i) {
                        if(!(S & (1 << i))) continue;
                        for(auto const to : nfa[i][x]) {
                            nS |= 1 << to;
                        }
                    }
                    dfa[S][x] = nS == 0 ? -1 : nS;
                    if(nS == 0 || vis.count(nS)) continue;
                    que.push(nS);
                    vis.insert(nS);
                }
            }
        }

        map<int, ll> memo;
        function<ll(int)> solve = [&] (int S) {
            if(memo.count(S)) return memo[S];
            if(S == (1 << fin)) return 1LL;
            for(int x = 0; x <= 9; ++x) {
                if(dfa[S][x] == -1) continue;
                memo[S] += solve(dfa[S][x]);
            }
            if(S & (1 << fin)) {
                memo[S] += 1;
            }
            return memo[S];
        };

        cout << solve(1) << endl;
    }
}

感想

これむずい。
TDPC の文字列作るやつに似てるから1文字ずつ付け加えていって、無理やり一意的な表現にしようとしたけど無理だった。