TopCoder SRM 840 : Div1 Medium AlternatingPermutations

またコーナーケース漏れ…。
https://community.topcoder.com/stat?c=problem_statement&pm=17878

問題

0～(N-1)の順列のうち、以下を満たすものは何通りか。

• 階差数列を取ると、正負の値が交互に並ぶ。
• prefix部分が指定された入力と等しい。

解法

まずコーナーケースを取り除こう。

• prefixの時点で、正負の条件に合わなかったり同じ値が複数ある場合は、解は0
• N=1なら、解は1

あとは以下を考えればよい。
f(n,m) := n要素目まで決めたとき、n要素目の値は、n要素目及びn要素目以降のうちm番目に小さい。また、直前の値より大きい
g(n,m) := n要素目まで決めたとき、n要素目の値は、n要素目及びn要素目以降のうちm番目に小さい。また、直前の値より小さい

f(n,m)やg(n,m)の累積和から、f(n+1,m)やg(n+1,m)が求められる。
prefixの値から、f(|prefix|,m),g(|prefix|,m)を求め、そこからf(N,0)やg(N,0)を答えよう。

const ll mo=1000000007;

ll from[7005][2];
ll to[7005][2];

class AlternatingPermutations {
	public:
	int count(int N, vector <int> prefix) {
		
		int i;
		set<int> S;
		FORR(p,prefix) {
			if(S.count(p)) return 0;
			S.insert(p);
		}
		
		if(prefix.size()>=3) {
			for(i=2;i<prefix.size();i++) if((prefix[i]-prefix[i-1])*(prefix[i-1]-prefix[i-2])>=0) return 0;
		}
		
		if(prefix.size()==N||N==1) return 1;
		
		ZERO(from);
		if(prefix.empty()) {
			FOR(i,N) from[i][0]=from[i][1]=1;
		}
		else if(prefix.size()==1) {
			from[prefix[0]][0]=from[prefix[0]][1]=1;
		}
		else {
			int le=prefix.back();
			FORR(p,prefix) if(p<prefix.back()) le--;
			if(prefix[prefix.size()-2]<prefix[prefix.size()-1]) from[le][1]=1;
			else from[le][0]=1;
			N-=prefix.size()-1;
		}
		
		
		while(N>1) {
			ZERO(to);
			
			//up
			ll sum=0;
			FOR(i,N) {
				(sum+=from[i][0])%=mo;
				to[i][1]=sum;
			}
			//down
			sum=0;
			for(i=N-1;i>=1;i--) {
				(sum+=from[i][1])%=mo;
				to[i-1][0]=sum;
			}
			
			
			swap(from,to);
			N--;
		}
		return (from[0][0]+from[0][1])%mo;
	}
}

まとめ

N=1のケースで見事に落とした…。