TopCoder SRM 555 Div2 Hard MuddyRoad2

自分がTopCoderに本格参戦してからのSRM Div2Hard/Div1Mediumは全部解いたので、まだ本格参戦してない頃のDiv2 Hardを３問解いてみた。
どれもノーヒントで行けたし、Div2 HardはDiv1 Mediumよりはラクかな。
http://community.topcoder.com/stat?c=problem_statement&pm=12189

問題

0～(N-1)番までのNマスが１列に並んでおり、0番と(N-1)番の除くマスのうちMマスはぬかるんでいる。
0番のマスから(N-1)番のマスに以下を満たしながら移動する。

• １度に１マスまたは２マス分、番号を増やす方向に移動できる。
• ぬかるんだマスに停止しない。（２マス移動で通過するのはよい）

Mマスのぬかるみの配置のうち、移動手順の組み合わせが偶数通りになるような配置の組み合わせを求めよ。

解法

最初「偶数手で到着できる配置か、簡単だな」と思ったら、「到着手順が偶数通りになる配置」だった。

到着手順が偶数通りになる配置を求めるのは面倒なので、全体の組み合わせから奇数通りになる配置を引く方が楽。

移動手順が奇数通りになるには、ぬかるんだマスに挟まれたぬかるんでないマスの先頭から最後までの移動手順が奇数になればよい。
移動手順の総数は、そのようなぬかるんでない各連続マスの移動手順の積なので、１個でも偶数通りとなるような連続マスがあると、全体の移動手順も偶数通りになる。

ぬかるんでない連続マスの移動手順は実質フィボナッチ数列になっており、連続マスが1,2,4,5,7,8…3K+1,3K+2,3(K+1)+1,,,,だったら奇数になる。

まとめると、ぬかるんでない(N-M)個のマスを、M個のぬかるみマスの前後の計(M+1)箇所に割り振り、かつ各割り振られたマス数が上記(3K+1),(3K+2)の形になっていればよい。
この処理はO(N^2*M)で終わるので、N<=50なら時間は余裕。

ll fib[1000];
ll dpdp[1000][1000];
ll mo=555555555;

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	return C_[P_][Q_];
}


class MuddyRoad2 {
	public:
	int theCount(int N, int muddyCount) {
		int x,y,i;
		ll tot=comb(N-2, muddyCount);
		fib[1]=fib[2]=1;
		for(i=1;i<=N;i++) fib[i+2]=(fib[i]+fib[i+1])%2;
		
		ZERO(dpdp);
		dpdp[0][0]=1;
		FOR(x,muddyCount+1) FOR(y,N-muddyCount+1) if(dpdp[x][y]) {
			for(i=1;i<=N-muddyCount-y;i++) if(fib[i]) dpdp[x+1][y+i]=(dpdp[x+1][y+i]+dpdp[x][y]) % mo;
		}
		
		return (int)((mo+(tot-dpdp[muddyCount+1][N-muddyCount])%mo)%mo);
	}
};

まとめ

M個のぬかるみマスの間にぬかるんでないマスを配置する、と考えると一気に簡単になるね。