Educational DP Contest : T - Permutation

遅れた参加したこともあり時間切れ。一応全部自力で解けた。
https://atcoder.jp/contests/dp/tasks/dp_t

問題

整数Nが与えられるので、1～NのPermutation Pを構築することを考える。
その際、隣接要素の大小関係が指定される。
その関係を満たすものが何通りあるかを答えよ。

解法

以下を考える。f(N-1,0)が解である。
f(i,k) := P[0]～P[i]までを決めたとき、i番目は残された数字のうち小さい方からk番目であるような時の組み合わせ

P[i]＞P[i+1]が指定されていたとすると、f(i+1,m)=sum(f(i,m+1)...f(i,*))である。
同様にP[i]＜P[i+1]も処理できる。
これはf(i,*)を一通り求めた後毎回累積和を取っておけば、全体でO(N^2)で処理できる。

int N;
string T;
ll from[3030],to[3030];
ll S[3030];

ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>T;
	
	FOR(i,N) from[i]=1;
	
	FOR(i,N-1) {
		ZERO(to);
		FOR(x,N+1) S[x]=((x?S[x-1]:0)+from[x])%mo;
		FOR(x,N-1-i) {
			if(T[i]=='>') to[x]=(S[N]+mo-S[x])%mo;
			else to[x]=S[x];

		}
		swap(from,to);
	}
	cout<<from[0]<<endl;
	
}

まとめ

本番このあたりで手が痛くなってきた。