エレベーターホール・ナンバー (AOJ2587)
問題:N(<=6)個の数字を並べた時に出来る数は何通りか.各数字はa[i]以上b[i]以下をわたる.1<=a[i]<=b[i]<=99.
頭2,実装4,ライブラリ4みたいな解法と頭4実装2ライブラリ0みたいな解法がある.
前者の解法は,出来る数字を受理するNFAをつくる→power constructionでDFAにする→topological順序でDPする というだけ
NFA,DFA,minimizeDFA,NFAtoDFAあたりは持ってなかったので書いてライブラリにした
後者は半分全列挙+包除.
コード(前者)
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef vector<int> vi; struct DFA{ int Q; //state int A; //alphabet vector<vi> t; int q0; vi F; DFA(){} DFA(int Q,int A,vector<vi> t,int q0,vi F) :Q(Q),A(A),t(t),q0(q0),F(F){} }; struct NFA{ int Q; int A; vector<vector<vi> > t; int q0; vi F; NFA(int Q,int A,vector<vector<vi> >t,int q0,vi F) :Q(Q),A(A),t(t),q0(q0),F(F){} DFA NFAtoDFA(){ int DN=1; vector<vi> dt(1,vi(A,0)); vi DF; map<vi,int> mp; //sets->id queue<vi> que; que.push(vi{q0}); mp[vi{q0}]=0; while(!que.empty()){ vi vc=que.front();que.pop(); bool isF=0; for(int f:F) for(int v:vc) if(f==v) isF=1; if(isF) DF.pb(mp[vc]); rep(i,A){ vi nvc; for(int v:vc){ for(int u:t[v][i]) nvc.pb(u); } sort(all(nvc));nvc.erase(unique(all(nvc)),nvc.end()); if(!mp.count(nvc)){ mp[nvc]=DN++; dt.pb(vi(A,0)); que.push(nvc); } dt[mp[vc]][i]=mp[nvc]; } } return DFA(mp.size(),A,dt,0,DF); } }; typedef long long ll; ll dp[1000]; bool vis[1000]; vector<int> vc; DFA M; void dfs(int v){ vis[v]=1; rep(i,10) if(!vis[M.t[v][i]]) dfs(M.t[v][i]); vc.pb(v); } int main(){ while(true){ int N,a[6],b[6]; cin>>N; if(N==0) break; rep(i,N) cin>>a[i]>>b[i]; int Q=4*N+1,A=10,q0=0; vector<int> F; F.pb(4*N); vector<vector<vi> > t(Q,vector<vi>(A,vi{})); rep(i,N){ int x=a[i]/10,y=b[i]/10; rep(j,10){ if(a[i]<=j&&j<=b[i]) t[4*i][j].pb(4*i+4); } if(x>0){ t[4*i][x].pb(4*i+1); rep(j,10) if(a[i]<=x*10+j&&x*10+j<=b[i]) t[4*i+1][j].pb(4*i+4); } if(x+1<y){ for(int j=x+1;j<y;j++) t[4*i][j].pb(4*i+2); rep(j,10) t[4*i+2][j].pb(4*i+4); } if(x<y){ t[4*i][y].pb(4*i+3); rep(j,10) if(a[i]<=y*10+j&&y*10+j<=b[i]) t[4*i+3][j].pb(4*i+4); } } M=NFA(Q,A,t,q0,F).NFAtoDFA(); queue<int> que; N=M.Q; rep(i,N) dp[i]=0,vis[i]=0; dp[M.q0]=1; vc.clear(); dfs(M.q0); reverse(all(vc)); for(int v:vc){ rep(i,10) dp[M.t[v][i]]+=dp[v]; } ll ans=0; for(int f:M.F) ans+=dp[f]; cout<<ans<<endl; } }