読者です 読者をやめる 読者になる 読者になる

エレベーターホール・ナンバー (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;
	}
}