Kawazoe(@riverplus)さんのCodeIQの問題です。
問題と他の情報がこちらにあります。
->https://posfie.com/@riverplus/p/U6B4suM
問題->30個の碁石を並べるとき、もっとも長い黒石の連続した個数が
5個となるような並べ方は全部で何通りあるでしょうか？
最初に考えたのはごく普通のメモ化再帰プログラムです。
これで十分余裕があります。
石をk個置いた時点で最後の石からの黒石の連続数がv、
その時点での最長の黒石の連続数がmaxの時の並べ方の数がf(k,v,max)です。
それは次に黒を置いた場合f(k+1,v+1,max1)と
次に白を置いた場合f(k+1,0,max)の合計です。
v+1が今までの最長maxより長ければmax1はv＋1になり、
そうでなければmaxのままです。
最後の石を置いたときmaxがmと等しければ1をそうでなければ0を返します。
#julia ver 1.41,1.53,1.85,1.12.1
function solve(n,m,a)
function f(k,v,max)
if haskey(dic,(k,v,max))
return dic[(k,v,max)]
elseif v > m
return 0
elseif k == n
if max == m
return 1
else
return 0
end
end
if v+1 > max
max1 = v+1
else
max1 = max
end
return dic[(k,v,max)] = f(k+1,v+1,max1)+f(k+1,0,max)
end
dic = Dict()
ret = f(0,0,0)
s = a == ret ? "ok " : "no "
println(s,ret)
end
solve(30,5,189489255)
Prologではmaxのところをそれまでの最長がMなら２,
M未満なら1の符号に変えました。
Iが置いた石の数、Vが最後の石からの黒の連続数、Sが符号です。
I個並べた時点でVがM-1なら、次の石が黒でSが2になる場合と、
次の石が白でSがそのままの場合の数の合計を求めて配列[I,V,S]に入れます。
I個並べた時点でVがMなら、次の石が白で連続の並びが0、
符号は2の場合だけ調べます。
その他の場合は、次の石が白と黒の両方の場合の数を足して配列に入れます。
IがNと等しくなった時、符号Sが2なら１を0なら0を配列[N,V,S]]に入れます。
最後に配列の[1,1,1]に入っている値が求める結果です。
functorとargを使って三次元配列を作り、そのインデックスに合わせて、
0からでなく１から始めていますので、N,M,I,Vを調整しています。
%SWI-Prolog ver 7.42,7.64,9.29
%:-initialization(start). %ideone,Online Prolog Compiler
%start.
twoar(_,0,_). % two dimensional array
twoar(F,X,Z):-arg(X,F,V),functor(V,z,Z),X1 is X-1,twoar(F,X1,Z).
data(F,X,Z,V):-arg(X,F,V1),arg(Z,V1,V).
triar(_,0,_,_). % three dimensional array
triar(F,X,Y,Z):-arg(X,F,V),functor(V,y,Y),twoar(V,Y,Z),X1 is X-1,triar(F,X1,Y,Z).
data(F,X,Y,Z,V):-arg(X,F,V1),arg(Y,V1,V2),arg(Z,V2,V).
%fn(N,M,I,V,S,F):-
% (S=:=1,M-V>N-I),!,data(F,I,V,K,0).
fn(N,_,N,V,S,F):-
!,(S=:=2->R=1;R=0),data(F,N,V,S,R).
fn(_,_,I,V,S,F):-
data(F,I,V,S,R),nonvar(R),!.
fn(N,M,I,V,S,F):-
V =:= M-1,!,I1 is I+1,V1 is V+1,fn(N,M,I1,V1,2,F),data(F,I1,V1,2,R1),
fn(N,M,I1,1,S,F),data(F,I1,1,S,R2),R is R1+R2,data(F,I,V,S,R).
fn(N,M,I,V,S,F):-
V =:= M,!,I1 is I+1,fn(N,M,I1,1,2,F),data(F,I1,1,2,R),data(F,I,V,S,R).
fn(N,M,I,V,S,F):-
I1 is I+1,V1 is V+1,fn(N,M,I1,V1,S,F),data(F,I1,V1,S,R1),
fn(N,M,I1,1,S,F),data(F,I1,1,S,R2),R is R1+R2,data(F,I,V,S,R).
solve(N,M,F,R):-fn(N,M,1,1,1,F),data(F,1,1,1,R).
start:-
f(N,M,A),N1 is N+1,M1 is M+1,functor(F,x,N1),triar(F,N1,M1,2),
(solve(N1,M1,F,R)->(R==A->Str=" ok ";Str=" no ");write(fail)),write(" "),write(Str),writeln((N,M)->R).
f(30,5,189489255).
ところで投稿する前にたまたま
https://qiita.com/riverplus/items/0333155df145f1c3ae16
で同じ趣旨の問題でn=10^5、m=10^4の問題を見つけてしまいました。
上のコードではメモリーも時間もとても間に合いません。
n+1列の配列ではなく2列の配列でひとつ前と後の状態を繰り返し表す方法や
行列の積による計算もかなり時間が超過します。
そこでもう一度実際に数字を書き出したりして考え直しました。
i番目の碁石を置いたときにj個連続している場合、
すでにm個連続した石がある場合の数をf(i,j,1),ない場合をf(i,j,0)で表すと
i-1番目の時黒石がいくつ連続していても、
i番目が白石だと連続数は0になりますので、
f(i,0,_)はf(i-1,0,_)からf(i-1,m,_)までを足したもの、
またf(i-1,k,_)はf(i-1-k,0,_)ですので、
f(i,0,_)はf(i-m,0,_)からf(i-1,0,_)を足したものになります。
但し、f(i,0,0)にはf(i,m,0)は含まれません。そしてf(i,0,1)には
f(i-1,m,0)=f(i-m-1,0,0)が加わります。
f(i,_,_)がすべてf(_,0,_)で表せますので、f(_,0,_)に絞ります。
実際のコードではf(i,0,0)はar1[i+1]で,f(i,0,1)はar2[i+1]で,
それぞれの碁石0個からの累積和をそれぞれsum1,sum2で表しています。
ar1[i]はi-1までのar1の累積和sum1[i-1]からi-m-1までの累積和sum1[i-m-1]を
引いたものです。
ar2[i]はi-1までのar2の累積和sum2[i-1]からi-m-2までの累積和sum2[i-m-2]を
引いてar1[i-m-1]をたしたものです。
答えはn個の碁石を並べた後のf(n+1,0,1)の値すなわちar2[n+2]です。
問題の答えは見つかりませんが、小さな数で検証した結果は他の方法と一致します。
#julia ver 1.41,1.53,1.85
function solve(n,m)
n += 1
r = 10^6
ar1 = zeros(Int,n+1)
sum1 = zeros(Int,n+1)
ar2 = zeros(Int,n+1)
sum2 = zeros(Int,n+1)
ar1[1],sum1[1] = 1,1
for i in 2 : n + 1
ar1[i] = mod(sum1[i-1],r)
if i > m + 1
ar1[i] = mod(ar1[i] - sum1[i-m-1],r)
ar2[i] = mod(sum2[i-1] + ar1[i-m-1],r)
if i > m + 2
ar2[i] = mod(ar2[i] - sum2[i-m-2],r)
end
end
sum1[i] = mod(ar1[i] + sum1[i-1],r)
sum2[i] = mod(ar2[i] + sum2[i-1],r)
end
println(ar2[end])
end
solve(10^5,10^4)