UnKoder #03 : Rabbit Family

これが一番おもしろかったです。
https://www.hackerrank.com/contests/unkoder-03/challenges/rabbit-family

問題

0日目には小さい兎が１羽いる。
1日ごとに各兎は以下のように増える。

• 小さい兎は１日で大きくなる。
• 既に大きい兎は、１日ごとに１羽小さな兎を生む。

ここで、N日後にいる兎の一部に首輪をかける。
直接の親子関係にある兎両方に首輪をかけない組み合わせは何通りあるか。

解法

再帰またはDPで解ける。
ただ自分の場合再帰ではメモリ不足かSegFaultを起こしたので、DPで置きなおした。

首輪のあるまたはない兎が１羽いたとき、L日後首輪の組み合わせがどうなるかをf(L,n)とする。
(n=1:首輪あり, n=0:首輪なし)

• n=1の時、生んだ兎は首輪を付けられない。生んだ兎は２日後から新たな兎を生み、また今見ている兎は翌日も兎を生むのでf(L,1) = f(L-1,1) * f(L-2,0)
• n=0の時、生んだ兎は首輪を付けてもつけなくても良いので、以下同上の考察によりf(L,0) = f(L-1,1) * (f(L-2,0) + f(L-2,1))

以下のコードのコメント部は、最初SegFaultを起こした再帰版である。

ll N;
ll mo=1000000007;
ll memo[1010000][2];

/*
ll dodo(int left,int ring){
	if(left<=0) return 1;
	
	ll& ret=memo[left][ring];
	if(ret>=0) return ret;
	
	ret=0;
	if(ring) {
		ret = dodo(left-1,1) * dodo(left-2,0) % mo;
	}
	else {
		ret = dodo(left-1,0) * (dodo(left-2,0)+dodo(left-2,1)) % mo;
	}
	return ret;
}
*/

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	
	memo[0][0]=memo[0][1]=1;
	memo[1][0]=memo[1][1]=1;
	
	for(i=2;i<=N;i++) {
		memo[i][0]=memo[i-1][0] * (memo[i-2][0]+memo[i-2][1]) % mo;
		memo[i][1]=memo[i-1][1] * memo[i-2][0] % mo;
	}
	cout<<(memo[N][0]+memo[N][1])%mo<<endl;
}

まとめ

こういう問題を考えられるようになりたい。