CodeIQ:「ループ・トラッキング」問題の解答

Kawazoe(@riverplus)さんのCodeIQの問題です。
問題とテストケースはこちらの御世話になりました。解答もあります。
->https://blog.goo.ne.jp/r-de-r/e/34be3bec8369a54df72d8c95ba8abe08
(リンク切れしていました。2025.5.2)
URL変わっていましたが見つかりました。(2025.5.3追加)
->https://sangaku0418.hatenablog.com/entry/2017/10/26/100100
こちらにも情報があります。
->https://togetter.com/li/1165676

ーーー2025.5.2追加
Fn(x)=floor(4x(n-x)/n))と定義します。
(0<=k<=n)なる整数kに対し、Fn(k)=k1->Fn(k1)=k2->Fn(k2)=k3...
という操作を繰り返すと、いずれ同じ値が出ます。
その時までの変換回数をG(n,k)とします。
0<=k<=nのすべてのkに対するG(n,k)の和を求める問題です。
ーーー

Fn=<nなので必ず循環します
数はa->b->c->[d->e->f]->d->e->f....のようになりますので、G(n,k)=G(k)とすると
この例の場合G(d)=G(e)=G(f)=3,G(a)=3+3,G(b)=2+3,G(c)=1+3となります。
dic[x]=G(x)とメモ化します。
G(k)を計算するときは
ar[1]=k,その後ろにFnの計算結果a,b...を入れていくとして、
ar[v]の値が辞書に存在したら、
1<=i<=vとなるiに対してdic[ar[i]]=v-(i-1)+dic[ar[v]]
辞書にないままm<vに対しar[v]=ar[m]となったら
1<=i< m->dic[ar[i]] = (m-i)+(v-m)+1
m<=i<=v->dic[ar[i]] = (v-m)+1
更にsum+=dic[ar[1]]としてG(k+1)の計算に移ります。
最後のsumの値が答えです。
途中でsumを計算せず、最後にまとめて辞書の値を足しても良いです。

#julia ver 1.41,1.53,1.73

function solve(n,a)
   dic = Dict{Int,Int}()
   len, sum = 0, 0
   for x0 in 0:n
       x = x0
       v = 0
       ar = [x0]
       while true
           if haskey(dic,x)
               for i in 1:v
                 dic[ar[i]] = v - (i -1) + dic[x]
               end  
               sum += v + dic[x]   #dic[ar[1]]
               break
           end
           x = Int(floor(4*x*(n-x)/n))
           v += 1
           if in(x,ar)
               m = findfirst(ar.==x)
               for i in 1:m-1
                   dic[ar[i]] = v - i + 1
               end
               for i in m:v
                  dic[ar[i]] = v - m + 1
               end
               sum += v        #di[ar[1]]
               break
           else
               push!(ar,x)
           end
       end
   end
   s = a == sum ? "ok " : "no "
   println(s,sum)
end

solve(10,42)
solve(20,91)
solve(100,1118)
solve(35, 226)
solve(350, 8877)
solve(1908, 99344)
solve(61922, 8504585)
solve(99999, 35499513)
solve(299997, 204796803)

Prologではideoneで最大2秒弱かかります。

functor/3でメモ化用の配列（F）を作り、arg/3で入出力を行います。
0<=Fn(x)<=NなのでFの要素数はN+1。F[Fn(X)+1]=G(Fn(X))。
fn202/7の最初の節のnumber(V1)が成功すれば、リストの最後の値が辞書にあり、
その時の操作をputat0/5で行っています。
失敗した場合は、X1＝Fn(X)を計算し、
リストの中にX1があればputat1/5で同じ数が出現した場合の操作を行い、
なければリストにX1を加え、fn202/7の最初の節に行きます。

%SWI-Prolog ver 7.42,7.64
%:-initialization(start).   %ideone
%start.

putat0(_,0,_,_,F).
putat0(N,I,V,L,F):-
    nth1(I,L,X),X1 is X+1,N1 is N-(I-1)+V,arg(X1,F,N1),I1 is I-1,putat0(N,I1,V,L,F).

putat1(I,_,V,_,F):-V<I,!.
putat1(I,M,V,L,F):-
    (I<M->V1 is V-I+1;V1 is V-M+1),nth1(I,L,X),X1 is X+1,
    arg(X1,F,V1),I1 is I+1,putat1(I1,M,V,L,F).

fn202(N,Y,X,F,V,L,R):-
    X1 is X+1,arg(X1,F,V1),number(V1),!,putat0(V,V,V1,L,F),V2 is V1+V,R=V2.
fn202(N,Y,X,F,V,L,R):-
    X1 is floor(4*X*(N-X)/N),V1 is V+1,
    (nth1(M,L,X1)->(putat1(1,M,V1,L,F),R=V1);(append(L,[X1],L1),fn202(N,Y,X1,F,V1,L1,R))).

fn201(N,Y,F,R):-fn202(N,Y,Y,F,0,[Y],R).

fn20(N,-1,F,R,R).
fn20(N,Y,F,R1,R):-fn201(N,Y,F,R2),R3 is R1+R2,Y1 is Y-1,fn20(N,Y1,F,R3,R).

solve(N,A):-N1 is N+1,functor(F,x,N1),
   (fn20(N,N,F,0,R)->(R==A->Str=" ok  ";Str=" no  ");
    write(fail)),write(" "),write(Str),writeln(R),!.

start:-f(N,A),solve(N,A),fail.
start.

f(10,42).
f(20,91).
f(100,1118).
f(35, 226).
f(350, 8877).
f(1908, 99344).
f(61922, 8504585).
f(99999, 35499513).
f(299997, 204796803).