Codeforces #274 Div1 C. Riding in a Lift

またもしょうもないミスをやらかした問題。
http://codeforces.com/contest/480/problem/C

問題

N階建ての建物があり、初期状態でA階にいる。
ここでエレベータに乗ると、エレベータは以下のように動く。

• 今X階にいるとき、秘密のB階に到達しうる距離は移動できない。すなわち移動先Y階はX!=Yかつ|X-Y| ＜ |X-B|となるように動く。

計K回エレベータを利用するとき、移動経路の組み合わせ数を答えよ。

解法

A＞Bの場合があるので、その場合上下反転させておく。
(自分はこれやり忘れてWA出した)

するとあとはNの事は忘れて1～(B-1)階の間で移動すればよい。
配るDPではなく貰うDPを使い、「１回のY階に来るパターンは、直前にY階以外の1階～(Y+(B-Y-1)/2)階のどこかにいる場合」なので、毎回1～X階までにいるパターンの総和を求めておくことで、O(KB)で処理できる。

ll N,A,B,K;
ll mo=1000000007;
ll dp[5020][5020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B>>K;
	if(B<A) {
		A=N+1-A;
		B=N+1-B;
	}
	
	for(x=A;x<B;x++) dp[0][x]=1;
	
	FOR(i,K) {
		for(x=1;x<B;x++) {
			int up=x+(B-x-1)/2;
			dp[i+1][x]=dp[i][up]-(dp[i][x]-dp[i][x-1]);
			dp[i+1][x]=(((dp[i+1][x]+dp[i+1][x-1])%mo)+mo)%mo;
		}
	}
	cout << dp[K][B-1] <<endl;
}

まとめ

ABの制限の見落としというしょうもないミスがもったいない。