Codeforces #314 Div2 F. Mausoleum

結果的にはこちらの方がEより簡単に感じた。
http://codeforces.com/contest/567/problem/F

問題

1～Nの整数２個ずつ、計2*N要素からなる数列を作りたい。
以下の条件を満たす数列は何通りできるか。

• 数列の値を順に見ていくと、上に凸である。
• いくつか数列要素の２値比較に対する不等式が与えられる。これらの不等式をすべて満たす。

解法

まずNは２個隣接していないと凸にできないのは明らか。
よってN２個の位置は総当たりしよう。
以下、(N-1)、(N-2)…と順に決めていくわけだが、全体を凸にするには各数字はすでに決まった要素群に隣接させないといけない。
よって数字の埋め方は以下のいずれかになる。

• すでに決まった要素群の左に２個つける
• すでに決まった要素群の右に２個つける
• すでに決まった要素群の左右に１個ずつつける

すでに決まった要素群の左右端の位置を状態とし、メモ化再帰などで次の要素の埋め方を上記３通り総当たりしていけばよい。
その際、新規追加要素に対し、数式の条件に合うかどうか適宜判定していく。
全体としては状態数分O(N^2)で間に合う。

int N,K;
int X[101],Y[101];
string S[101];
vector<int> V[101];
ll ret;
ll dp[101][101];

int okok(int lo1,int lo2,int hi1,int hi2,int x,int y,string s) {
	int xv=0,yv=0;
	if(hi1<=x && x<=hi2) xv=2;
	else if(x==lo1 || x==lo2) xv=1;
	if(hi1<=y && y<=hi2) yv=2;
	else if(y==lo1 || y==lo2) yv=1;
	
	if(s=="=") return xv == yv;
	if(s=="<") return xv < yv;
	if(s==">") return xv > yv;
	if(s=="<=") return xv <= yv;
	if(s==">=") return xv >= yv;
	return 0;
}

ll dpdp(int L,int R) {
	if(R-L+1==2*N) return 1;
	if(L<0 || R>=2*N) return 0;
	if(dp[L][R]>=0) return dp[L][R];
	ll ret=0;
	
	if(L>=2) {
		int ok=1;
		FORR(r,V[L-1]) ok &= okok(L-2,L-1,L,R,X[r],Y[r],S[r]);
		FORR(r,V[L-2]) ok &= okok(L-2,L-1,L,R,X[r],Y[r],S[r]);
		if(ok) ret += dpdp(L-2,R);
	}
	if(L>=1 && R<=2*N-2) {
		int ok=1;
		FORR(r,V[L-1]) ok &= okok(L-1,R+1,L,R,X[r],Y[r],S[r]);
		FORR(r,V[R+1]) ok &= okok(L-1,R+1,L,R,X[r],Y[r],S[r]);
		if(ok) ret += dpdp(L-1,R+1);
	}
	if(R<=2*N-3) {
		int ok=1;
		FORR(r,V[R+1]) ok &= okok(R+1,R+2,L,R,X[r],Y[r],S[r]);
		FORR(r,V[R+2]) ok &= okok(R+1,R+2,L,R,X[r],Y[r],S[r]);
		if(ok) ret += dpdp(L,R+2);
	}
	return dp[L][R]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) {
		cin>>X[i]>>S[i]>>Y[i];
		X[i]--;
		Y[i]--;
		V[X[i]].push_back(i);
		V[Y[i]].push_back(i);
	}
	
	MINUS(dp);
	FOR(i,2*N-1) {
		int ok=1;
		FORR(r,V[i]) ok &= okok(i,i+1,i,i+1,X[r],Y[r],S[r]);
		FORR(r,V[i+1]) ok &= okok(i,i+1,i,i+1,X[r],Y[r],S[r]);
		if(ok) ret+=dpdp(i,i+1);
	}
	cout<<ret<<endl;
	
}

まとめ

O(N^2*K)程度で間に合う気がするが、なんでこんな制限緩いんだろう。
N上限100でもいいのに。