#バージョン1
ある日に、それぞれのサイズのバイバイマンが何人いたかわかっていたら、翌日のバイバイマンが計算できる。
C# (138B)
class P{static void Main(){long a=1,b=0,c=0,d=0,e=0,i=0,t;for(;i++<100;){t=d;d=e;e=c;c=b;b=a+t;a=d+t;System.Console.WriteLine(b+c+d+e);}}}
F# (86B)
Seq.fold(fun(a,b,c,d,e)_->printfn"%d"(a+b+c+d+e);d+e,a+d,b,e,d)(1L,0L,0L,0L,0L){0..99}
#バージョン2
サイズは無視して、バイバイマンの数だけで漸化式ができるかもしれない。フィボナッチっぽく。
バージョン1では(バイバイマンの5種類のサイズに応じて)変数が5つだったので、漸化式もせいぜい5日分で構成できるはず。
やってみたら5日分では解がなく、4日分で解が求められた。
漸化式が使えるのは5日目からで、それまではバイバイマンは1人しかいないというのをそのままコードにしてみる。 (コード上は S[n-1]-S[n-2]+S[n-3]+S[n-4]) と、逆にして使っている )
C# (135B)
class P{static void Main(){var s=new long[100];for(int i=0;i<100;)System.Console.WriteLine(s[i++]=i<5?1:s[i-2]-s[i-3]+s[i-4]+s[i-5]);}}
#バージョン3
iが0以下の時のS(i)をうまく設定すれば、iによる条件分岐はいらないのでは?
→いらなかった。
初期値として (3, -1, 1, 0) を使って、あとは漸化式を適用するだけでいい。 (コード上は (0, 1, -1, 3) と、逆にして使っている )
C# (117B)
class P{static void Main(){long a=0,b=1,c=-1,d=3,i=0;for(;i++<100;)System.Console.WriteLine(a=d+(d=c)-(c=b)+(b=a));}}
F# (80B)
Seq.fold(fun(a,b,c,d)_->printfn"%d"(d+c-b+a);d+c-b+a,a,b,c)(0L,1L,-1L,3L){0..99}
ange1さんの解説がわかりやすい。
バイバイマンを数えように挑戦しました ( CodeIQ ) - ange1のブログ
ただ、自分の解答を元に発展させるとするなら、つまり
S[n]=S[n-1]-S[n-2]+S[n-3]+S[n-4]
が求められているのなら、これに
S[n-1]=S[n-2]-S[n-3]+S[n-4]+S[n-5]
を代入すると、S[n-1]-S[n-2]+S[n-3] が消えて
s[n]=2S[n-4]+S[n-5]
になるという……
あとはわかるな……と思ったけどゴルフするのは結構難しいかも。よく考えてみる。
F#のコード、ムダが多かった…… バージョン3の初期値をマイナスから始めずに、(1, 1, 1, 1) から始めた方が、計算式の重複を削れたじゃん。
F# (71B)
Seq.fold(fun(a,b,c,d)_->printfn"%d"d;d+c-b+a,a,b,c)(1L,1L,1L,1L){0..99}