Codeforces #223 Div1. D. Developing Game

これもRound 222程じゃないけどDiv1Dにしては簡単。
http://codeforces.com/contest/380/problem/D

問題

N個の席が並んでおり、各席には左右に飲み物入れが置いてある。
ここにN人の客が順に来る。
客は席に着くと、左右両側の飲み物入れを占有しようとする。
その際、両方ともすでに前の客に占有されていると、その客は怒って帰ってしまう。

N人の客の座った席の位置A[i]が与えられる。
ただし一部の客はどこに座ったか不明である。

客が誰も怒らず座れるような席順は何通りあるか答えよ。

解法

両隣両方に人が座っていると、その間には座れないことになる。
よって、最初の一人がどこかに座ると、後は既に座っている人たちの両隣どちらかに連結して座るしかない。

人が連続して座っている区間[L..R]に対し条件を満たす並びを数え上げていこう。
とはいえ１人１人行うと区間がO(N^2)通り出てきてTLE/MLEする。
そこで、席の位置が確定している人を中心に処理していこう。

席の位置が確定している人を座らせる場合、その前に席の位置が確定している人を座らせた後、位置が未確定の人を左に何人、右に何人座らせてあればいいかは簡単な計算で求められる。
左右の人数さえわかれば、combinationで位置が未確定な人の座り方が算出できる。

int N;
int A[101000];
map<int,int> M;
ll mo=1000000007;
vector<int> L,R,I;

ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}
ll comb(int P_,int Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll ret=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) ret=ret*(P_+1-i)%mo*modpow(i,mo-2)%mo;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		if(A[i]) M[A[i]]=i;
	}
	if(M.empty()) return _P("%lld\n",modpow(2,N-1));
	
	ITR(it,M) {
		I.push_back(it->second);
		if(it==M.begin()) {
			l=r=it->second;
			L.push_back(-2);
			R.push_back(-2);
		}
		else {
			if(it->second<l) {
				l=it->second;
				L.push_back(l);
				R.push_back(-2);
			}
			else if(it->second>r) {
				r=it->second;
				L.push_back(-2);
				R.push_back(r);
			}
			else return _P("0\n");
		}
	}
	L.push_back(0);
	R.push_back(N-1);
	for(i=L.size()-1;i>=0;i--) if(L[i]==-2) L[i]=L[i+1];
	for(i=L.size()-1;i>=0;i--) if(R[i]==-2) R[i]=R[i+1];
	
	ll lt=0,rt=0;
	x=M.begin()->first;
	y=M.begin()->second;
	map<pair<int,int>, ll> V;
	if(x==1) V[make_pair(y,y)]=1;
	else {
		if(y-L[0]>=x-1) V[make_pair(y-(x-1),y)]+=modpow(2,x-2);
		if(R[0]-y>=x-1) V[make_pair(y,y+(x-1))]+=modpow(2,x-2);
	}
	
	for(i=1;i<L.size()-1;i++) {
		map<pair<int,int>, ll> V2;
		
		ITR(it,V) {
			if(it->first.second<I[i]) {
				l=I[i]-(A[I[i]]-1);
				if(l<L[i] || l>it->first.first) continue;
				x=it->first.first-l;
				y=I[i]-it->first.second;
				V2[make_pair(l,I[i])] += comb(x+y-1,x)*it->second%mo;
			}
			if(I[i]<it->first.second) {
				r=I[i]+(A[I[i]]-1);
				if(r>R[i] || r<it->first.second) continue;
				x=it->first.first-I[i];
				y=r-it->first.second;
				V2[make_pair(I[i],r)] += comb(x+y-1,y)*it->second%mo;
			}
		}
		V=V2;
	}
	
	ll ret=0;
	ITR(it,V) {
		x=it->first.first;
		y=(N-1)-it->first.second;
		ret += comb(x+y,y)*it->second%mo;
	}
	cout<<ret%mo<<endl;
	
}

まとめ

映画館のカップ入れ、左右どっち使えばいいか迷うよね。
利き手の事を考えると一律左/右ともできないのかな。
取り外し式にして、左右のアームレストの好きな方につけられるとよさそう。