合計が 0 になるのは何通り？

当初の締め切りが 2/18 10:00AM なので，その 1 分後に投稿されるように予約する

自然数 n に対して、次の等式を考えます。
    □1□2□3□4…□n ＝ 0
四角の部分には、プラス（＋）またはマイナス（－）の記号が入ります。
等式を成立させるような記号の入れ方を考えましょう。
例えば、n = 7 のとき、次の 8 通りの入れ方が可能です。

    ＋1＋2－3＋4－5－6＋7 ＝ 0
    ＋1＋2－3－4＋5＋6－7 ＝ 0
    ＋1－2＋3＋4－5＋6－7 ＝ 0
    ＋1－2－3－4－5＋6＋7 ＝ 0
    －1＋2＋3＋4＋5－6－7 ＝ 0
    －1＋2－3－4＋5－6＋7 ＝ 0
    －1－2＋3＋4－5－6＋7 ＝ 0
    －1－2＋3－4＋5＋6－7 ＝ 0

自然数 n に対し、等式を成立させる記号の入れ方の数を F(n) と定義します。例えば F(7) = 8 です。
同様に、F(3) = 2、F(8) = 14 となることが確かめられます。
標準入力から、自然数 n （1 ≦ n ≦ 50）が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。

f = function(n, s) { # f(n, 0) で求まる
    if (n == 0) s == 0
    else if (abs(s) > n*(n+1)/2) 0
    else Recall(n-1, s-n) + Recall(n-1, s+n)
}

> f(3,0)
[1] 2
> f(7,0)
[1] 8
> f(8,0)
[1] 14

しかし，これでは，n = 50 なんてことになると，いつまで待っても答が返ってこない

そこで，以下のプログラムにする
瞬殺である

g = function(n) {
    d = 1
    for (m in 1:(n+1)) {
        len = length(d)
        i = ceiling(len/2)
        a = ifelse(i > len, 0, d[i])
        e = c(rep(0, 2*m), d)
        d = e+rev(e)
    }
    a
}

> options(digits=16)
> g(3)
[1] 2
> g(7)
[1] 8
> g(8)
[1] 14
> g(48)
[1] 1140994231458
> g(49)
[1] 0

gawk で --bignum を指定して

$ cat a.awk
function f(n) {
    len = 1
    d[len] = 1
    for (m = 1; n+1 >= m; m++) {
        i = int((len+1)/2)
        a = i > len ? 0 : d[i]
        for (j = 1; 2*m >= j; j++) {
            e[j] = 0
        }
        for (j = 1; len >= j; j++) {
            e[j+2*m] = d[j]
        }
        len += 2*m
        for (j = 1; len >= j; j++) {
            d[j] = e[j]+e[len+1-j]
        }
    }
    print a
}
BEGIN{
    f(48)
    f(100)
    f(101)
    f(102)
    f(103)
}

$ gawk --bignum --file=a.awk
1140994231458
1731024005948725016633786324
0
0
13252206944539668255309614628

成長と分裂

締め切りが 2/18 10:00 AM ということなので，1 分後に投稿されるように予約

バイバイマンのサイズを整数値で表します。
バイバイマンは 1 日毎に体の大きさが倍増します。
一番最初の大きさを「1」とし、1 日経つと 2 倍の「2」、さらに 1 日後は「4」というように、1 日毎に 2 倍になります。
また、一定の大きさをこえると分裂します。
バイバイマンは「1」→「2」→「4」→「8」→「16」と、大きさが 10 を超えたところで分裂します。
分裂後のサイズは、「16」なら「1」と「6」のように 10 の位の数と 1 の位の数になります。
分裂したバイバイマンは、再び大きくなります。
このようなルールで増えるバイバイマンの数を、1 日ごとに調べて、100 日目までを出力してください。
1 日目から 20 日目までは，1, 1, 1, 1, 2, 3, 3, 3, 5, 8, 9, 9, 13, 21, 26, 27, 35, 55, 73, 80 のようになります。

ブルートフォースでやると，とんでもない時間がかかる。
問題をよく調べて見ると，サイズが 1, 2, 4, 8, 6 のものがいくつあるかを数えておいて，次の段階でどのサイズがいくつになるかを整理するとよいことがわかる。
ということで，以下のような簡単なプログラムを得ることができる。
a[1]～a[5] は今の時点でサイズが 1, 2, 4, 8, 6 のものがいくつあるかを表す。次の段階ではそれぞれが 2 倍の大きさの場所に数えられる。ただし，前の段階でサイズ 8 のものは，次の段階では サイズ 1, 6 のものとして，前の段階でサイズ 6 のものは，次の段階では サイズ 1, 2 のものとして数えられる。

a = b = integer(5)
a[1] = 1
for (i in 1:100) {
    cat(sum(a), "\n", sep="")
    b[1] = a[4] + a[5]
    b[2] = a[1] + a[5]
    b[3:5] = a[2:4]
    a = b
}