[OCaml][C] ディビジョン・ナイン
@riverplus さんの CodeIQ 出題問題。
https://codeiq.jp/q/2561
http://togetter.com/li/956617
答案：整数分割問題として直接導出。
ざっと見た限り、見られる解き方は
- 0..8 mod9 の９連漸化式
- F(n,sum) の漸化式
- 1,2,3,4 の登場回数探索総あたり
くらい？
本稿は上記以外の解法となる。
なお、F(19) F(20) の導出には 64bit 整数処理が必要(倍精度浮動小数だとけた落ちする）。
導出過程
高校数学（現行課程なら数I) の知識で。
まず、必要な事実を列挙しておく。
- (n桁の)整数Ｎが９で割り切れる＝Ｎの各桁の数字の和が９で割り切れる、である。
- 整数Ｎに登場する数は1〜4のみであるから、Ｎの各桁の数字の和の上限は、4n である(下限はn)。
したがって、n が与えられた時、各桁の和が 9, 18, 27, ... で 4n 以下までを場合分けして探索する必要がある。
さて、登場可能な数を1〜4に限らず一般的に、和がsになるような0以上の整数(ここでは10以上もOKとして)分割を考える。特に、ちょうど n 個の非負整数に分割できるかどうかを考える。
と、これは単純な重複組み合わせである。nＨs = (s+n-1)Ｃ(n-1)
問題は非負整数ではないので、少しひねる必要がある。
まず、非負整数ではなく自然数、つまり０を除外することを考えると、各桁にまず1を分配してしまえば、残りは和がs-nになるようなn個の非負整数の分割問題に還元させることができる。
つまり、nＨ(s-n) = (s-1)Ｃ(n-1)
これだと、元の問題に対しては、各桁に５以上の数が含まれるケースも数え上げられてしまっているので、それを引かなければならない。
５以上の数が1つ以上含まれているケースは、nＨ(s-n-4) × nＣ1
５以上の数が2つ以上含まれているケースは、nＨ(s-n-4*2) × nＣ2
...
５以上の数がjつ以上含まれているケースは、nＨ(s-n-j*2) × nＣj
したがって、和がs になる、求める組み合わせ総数は、
F(n,s) = Σ(j=0 to n) ((-1)^j × nH(s-n-4*j)×nCj)
ゆえに総数は、
F(n)=Σ(s=9,18,..<=4n)Σ(j=0 to n) ((-1)^j × nH(s-n-4*j)×nCj)
となり、これをコーディングすればおしまい。
コード
CodeIQ 環境には nums.cma が組み込まれておらず Big_int 等が使えない。
let ( +% )=Int64.add
let ( -% )=Int64.sub
let ( *% )=Int64.mul
let ( /% )=Int64.div
let ( !% )=Int64.of_int
let ( !! )=Int64.to_string
let zero=Int64.zero
let one =Int64.one
let c n r=
let rec cc m i q=
let new_q=q *% (!% m) /% (!% i) in
if i<=r then cc (m+1) (i+1) new_q else q
in
if n0 then f_iter (i-9) (sum +% (fsub i n zero)) else sum
in
let sum=f_iter (n*4/9*9-n) zero in
print_endline !!sum
;;
f (read_int())
#include/* Calc. Combination nCr */ long long c(int n, int r) { long long q=1; int i,k; if( n 0; i-=9){ long long subsum=0; for(j=n; j>=0; j--) subsum = c(n,j) * c(i-j*4+n-1, n-1) - subsum; sum += subsum; } return sum; } int main() { int n; scanf("%d",&n); printf("%lld\n",f(n)); return 0; }
バイバイマン： アルゴリズム解説
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]+...)
であることが分かる。
あとはこの事実をゴルフすると上記のコードになる。
バイバイマンを数えよう
のコード解説。
採点環境では int=4byte (long も 4byte) なので C系、OCaml は double 等で対処しないとあふれる。
- Python
- これは提出していないけど最短タイ(50B)
r=1;q=p=s=0;exec"r,q,p,s=q,p,s-q,s+r;print s;"*100
let rec(@)s p q r=Printf.printf"%.f "s;s<6e10&(s+.r@s-.q)p q;;(1.@0.)0. 0.
- bc (44B)
- 最後の ;u= は標準入力を読み捨てるため。
- ループカウンタ変数はもったいないので停止条件がアレ
- z は一時退避用の変数
for(r=1;r<4^17;p=z){z=s-q;s+=r;s;r=q;q=p};u=
たてた
たぶんほとんど更新しないけど。
