AtCoder ARC #104 : C - Fair Elevator

久々のARC。
https://atcoder.jp/contests/arc104/tasks/arc104_c

問題

2N個のフロアがある建物が、N人が1回の昇りエレベーターで移動する。
各人が乗り降りした階の履歴が与えられる。
ただし一部は欠損している。

各フロアで乗り降りした人は合計1人だけである。
また、エレベーターで乗り合わせた人は、同じ移動階数だったことがわかっている。
履歴は条件を満たすものか判定せよ。

解法

後者の条件を考えると、もしk階移動した人がいた場合、連続してk個のフロアで人が乗ってきて、その後k個のフロアで人が下りた状態しかありえない。
そこで、以下を考える。
f(n,f) := 乗り降りしたフロアがともに未確定な人がf人いて、n階までの乗り降り履歴が確定済みのとき、それ以降の履歴は正しいか？

n階に続く何フロアで連続して人が乗ってくるかを総当たりしながらメモ化再帰しよう。

int N;
int A[101],B[101];
int T[202];
int isf;

int memo[202][202];

void dfs(int cur,int f) {
	if(cur==2*N) {
		cout<<"Yes"<<endl;
		exit(0);
	}
	if(memo[cur][f]==0) return;
	memo[cur][f]=0;
	
	int len;
	for(len=1;cur+len*2<=2*N;len++) {
		int cf=f;
		int x;
		for(x=cur;x<cur+len;x++) {
			if(T[x]>=N) break;
			if(T[x+len]>=0&&T[x+len]<N) break;
			if(T[x]>=0&&T[x+len]>=0&&T[x+len]!=T[x]+N) break;
			
			if(T[x]==-1&&T[x+len]==-1) cf--;
		}
		if(x==cur+len&&cf>=0) dfs(cur+len*2,cf);
	}
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	MINUS(T);
	MINUS(memo);
	FOR(i,N) {
		cin>>A[i]>>B[i];
		if(A[i]>=0) {
			A[i]--;
			if(T[A[i]]!=-1) return _P("No\n");
			T[A[i]]=i;
		}
		if(B[i]>=0) {
			B[i]--;
			if(T[B[i]]!=-1) return _P("No\n");
			T[B[i]]=i+N;
		}
		if(A[i]>=0&&B[i]>=0&&A[i]>=B[i]) return _P("No\n");
		if(A[i]==-1&&B[i]==-1) isf++;
	}
	
	
	dfs(0,isf);
	cout<<"No"<<endl;
}

まとめ

最初DFSで解いていて計算量が不安だったけど、メモ化すれば状態がさほど多くないことがわかって一安心。