バイバイマン： アルゴリズム解説

Golf OCaml

N日めのバイバイマンの数は漸化式で

  • S[N]=S[N-1]+(S[N-4]-S[N-6]+S[N-8]-S[N-10]+...)
  • S[1]=1

となる。上記コードでは r=(S[N-4]+...) になるように計算している。

導出過程

まず、バイバイマンをサイズ別に何体いるかを求めることを考える。

  • サイズ1: A[N]
  • サイズ2: B[N]
  • サイズ4: C[N]
  • サイズ8: D[N]
  • サイズ6: E[N]

バイバイマンのサイズはこの５通りしか登場しないので、S[N]=A[N]+B[N]+C[N]+D[N]+E[N] を最終的に出力できればよい。

N-1日目から１日経過したときの変化を考えると、

  • サイズ1: A[N]=D[N-1]+E[N-1] , A[1]=1
  • サイズ2: B[N]=A[N-1]+E[N-1]
  • サイズ4: C[N]=B[N-1]
  • サイズ8: D[N]=C[N-1]
  • サイズ6: E[N]=D[N-1]

と書ける。これをコード化してゴルフ圧縮してもそこそこの順位にはなる。(OCaml で以下のコードで 101B)

let rec(@)(a,b,c,d,e,s)n=Printf.printf"%.f
"s;n>0&(d+.e,a+.e,b,c,d,s+.a)@n-1;;(0.,1.,0.,0.,0.,1.)@99

さて、この５つの漸化式を全部足すと、

  • S[N]=S[N-1]+D[N-1]+E[N-1]

さらによく見るとD[N-1]+E[N-1]=A[N]なのだから、

  • S[N]=S[N-1]+A[N]

であり、サイズ１のバイバイマンの数がどうなるかだけ分かれば他のサイズは知ったことではないことが分かる。

しかし、A[N]を簡単に表現するのが難しい。一方、B[N] については上記漸化式から

  • B[N]=2B[N-4]+B[N-5]

という、サイズ２バイバイマンだけの６項間漸化式で表現できる。合計についてもサイズ２バイバイマンで表現し直すとこうなる。

  • S[N]=S[N-1]+B[N-3]+B[N-4]

この B[N] を一般式で求められるかというと、代数的には求めることは可能のはず(特性方程式(5次)が x+1 と x^4-x^3+x^2-x-1 に因数分解できる)。とはいえ、ゴルフ的に使えそうな簡単な式にはなりそうにない。このあたりまでの結果でゴルフをすると上位争いできる（場合によってはトップにもなれる）。

ここで、

  • S[N]=S[N-1]+D[N-1]+E[N-1]

に戻って、S だけの式にならないか式変形を試みる。

  • S[N]=S[N-1]+D[N-1]+E[N-1]
  • S[N]=S[N-1]+C[N-2]+D[N-2] ... ①
  • S[N]=S[N-1]+B[N-3]+C[N-3]
  • S[N]=S[N-1]+E[N-4]+A[N-4]+B[N-4]=S[N-1]+S[N-4]-(C[N-4]+D[N-4]) ... ②

①、②を比較すると、つまり、

  • C[N-2]+D[N-2]=S[N-4]-(C[N-4]+D[N-4])

なのだから、

  • C[N-2]+D[N-2]=S[N-4]-(C[N-4]+D[N-4])=S[N-4]-S[N-6]+(C[N-6]+D[N-6])=...
  • C[N-2]+D[N-2]=S[N-4]-S[N-6]+S[N-8]-S[N-10]+...

となる(S[1]かS[2]に到達するまで計算を続ける）。つまり、

  • S[N]=S[N-1]+(S[N-4]-S[N-6]+S[N-8]-S[N-10]+...)

であることが分かる。

あとはこの事実をゴルフすると上記のコードになる。