poj 2506 - A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2] 2007/09/28

2506 -- Tiling

うーん、こういう問題をさくっと解くためにはどういうアプローチでいけばいいんだろう。

ヒントになるかな
フィボナッチ数 - Wikipedia
代数的組合せ論
ドミノタイリング
とかかかな。

解答が思いつかなかったので、いつものごとくdiscussをチラ見して、

A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2]

をみつけていろいろためして、正しそうな答えがでてきたので、submitしたのだけど、WA(Wrong Answer)。

それでdiscussをチラ見したら、inputが0の時の解答がミソっぽい。0がinputの時、１をoutputしたらacceptされた。

うーん、よくわからない....

static BigInteger f(int n) {
// A[1]=1,A[2]=3,A[n]=A[n-1]+2*A[n-2]
final BigInteger TWO = BigInteger.valueOf(2);
BigInteger a1 = BigInteger.ONE;
BigInteger a2 = BigInteger.valueOf(3);
if (n == 0)
return BigInteger.ONE;
if (n == 1)
return a1;
if (n == 2)
return a2;
for (int i = 2; i < n; i++) {
BigInteger tmp = a2.add(TWO.multiply(a1));
a1 = a2;
a2 = tmp;
}

return a2;
}