Algoogle

Algorithm for Programming Contest

AOJ 2587 Elevator Hall Number

Category: AOJ Tag: dp, math

Elevator Hall Number

問題概要


n台のエレベーターが横に並んでいる.
各エレベーターは区間の間を移動できる.
各エレベーターの現在の階数をleading-0を許さずに並べて表示するとき, それらを繋げた数字は何種類あるか.

解法


NFAを作ってDFAに変換してDPする.
オートマトンについて基礎的な知識がある前提で話を進める.

NFAはあるエレベーターに対して以下のように作る.
大文字の英字が状態, 状態に矢印で挟まれたものは入力とする

*あるエレベーターについて開始状態をP, 終了状態をTとする

  • P -> 下限の10の位 -> Q
    ただし0の場合は遷移とする

  • P -> 上限と下限の10の位の間 -> R

  • P -> 上限の10の位 -> S

  • Q -> 下限の1の位から9まで -> T

  • R -> 0から9 -> T

  • S -> 0から上限の1の位 -> T

これらをエレベーター一つの塊としてn個のエレベーターを遷移で繋げば1つのNFAができる.

これから生成規則を除去する.

一つの状態から同じ入力で2つ以上の遷移先の候補がある場合は候補をひとまとめにした状態を新たに作って, そこから遷移させる.
ひとまとめにした状態の遷移先は, 元の状態の遷移先の和集合.
これを再帰的に行ってDFAをつくる.

今回はDPの都合のため逆辺を保存した.
あとは初期状態を1通りとして終了状態を含む状態からメモ化再帰して足し合わせればよい.

コード


(2587.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;

int n, l[8][2], h[8][2];
vector<int> nfa[64][16], fin;
vector<long long> dp;
vector<vector<int>> rdfa;
map<vector<int>,int> id;

void dfa_rec(int &st, vector<int> &nsts)
{
        int cur = st-1;
        id.insert(make_pair(nsts,cur));
        vector<int> next[10];
        for(auto &s: nsts) {
                if(fin[s]) fin[cur] = 1;
                for (int i = 0; i < 10; i++) {
                        for(auto &t: nfa[s][i]) {
                                next[i].push_back(t);
                        }
                }
        }
        for (int i = 0; i < 10; ++i) {
                sort(begin(next[i]),end(next[i]));
                next[i].erase(unique(begin(next[i]),end(next[i])), end(next[i]));
                auto it = id.find(next[i]);
                if(it == end(id)) {
                        rdfa.push_back(vector<int>());
                        fin.push_back(0);
                        rdfa.back().push_back(cur);
                        dfa_rec(++st, next[i]);
                }
                else rdfa[it->second].push_back(cur);
        }
}

int build_dfa()
{
        int st = 4*n+1;
        rdfa.assign(st,vector<int>());
        fin.assign(st,0);
        fin[st-1] = 1;
        for (int i = 0; i < 4*n+1; i++) {
                for (int j = 0; j < 10; j++) {
                        auto it = id.find(nfa[i][j]);
                        if(it == end(id)) {
                                rdfa.push_back(vector<int>());
                                fin.push_back(0);
                                rdfa.back().push_back(i);
                                dfa_rec(++st, nfa[i][j]);
                        }
                        else rdfa[it->second].push_back(i);
                }
        }
        return st;
}

void build_nfa()
{
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < 4; j++) id.insert(make_pair(vector<int>(1,4*i+j),4*i+j));
                int p = 4*i, q = p+1, r = q+1, s = r+1, np = s+1;
                if(h[i][1] == l[i][1]) {
                        if(h[i][1]) {
                                nfa[p][h[i][1]].push_back(s);
                                for (int j = l[i][0]; j <= h[i][0]; j++) nfa[s][j].push_back(np);
                        }
                        else for (int j = l[i][0]; j <= h[i][0]; j++) nfa[p][j].push_back(np);
                }
                else {
                        if(l[i][1]) {
                                nfa[p][l[i][1]].push_back(q);
                                for (int j = l[i][0]; j < 10; j++) nfa[q][j].push_back(np);
                        }
                        else for (int j = l[i][0]; j < 10; j++) nfa[p][j].push_back(np);

                        nfa[p][h[i][1]].push_back(s);
                        for (int j = 0; j <= h[i][0]; j++) nfa[s][j].push_back(np);

                        if(l[i][1] < h[i][1]-1) {
                                for (int j = l[i][1]+1; j < h[i][1]; j++) nfa[p][j].push_back(r);
                                for (int j = 0; j < 10; j++) nfa[r][j].push_back(np);
                        }
                }
        }
}

void init()
{
        for (int i = 0; i < 64; i++) {
                for (int j = 0; j < 16; j++) {
                        nfa[i][j].clear();
                }
        }
        rdfa.clear();
        dp.clear();
        fin.clear();
        id.clear();
}

long long rec(int cur)
{
        long long &ret = dp[cur];
        if(ret > 0) return ret;

        for(auto &s: rdfa[cur]) {
                ret += rec(s);
        }
        return ret;
}

long long solve()
{
        init();
        build_nfa();
        int st = build_dfa();
        dp.assign(st,0);
        dp[0] = 1;
        long long ans = 0;
        for (int i = 0; i < st; i++) {
                if(fin[i]) ans += rec(i);
        }

        return ans;
}

bool input()
{
        cin >> n;
        for (int i = 0; i < n; i++) {
                cin >> l[i][0] >> h[i][0];
                l[i][1] = l[i][0]/10;
                l[i][0] %= 10;
                h[i][1] = h[i][0]/10;
                h[i][0] %= 10;
        }
        return n;
}

int main()
{
        while(input()) cout << solve() << endl;
        return 0;
}

Comments