CodeIQ:長くなるように、増え続けるようにの解答

@nabetniさんのCodeIQの問題です。問題と解説はこちら。
->https://nabetani.hatenablog.com/entry/codeiq_incseq_q957
本来の問題の答えの値はこちらにお世話になりました。解答もあります。
https://github.com/suppy/CodeIQ/blob/master/CodeIQ-q957/answer1.txt

サンプル用に作ったPrologの末尾再帰系のメモ化では1000個のデータに太刀打ちできず、
Juliaで動的計画法やメモ化再帰で実装してみましたが、まだ時間がかかりました。
結局Prologでメモ化なしの全探索で枝刈したのが1秒以下の解答時間となりました。

dp/5->dp(L:入力値を数字のリスト化したもの,N:入力値の文字数,M:手前の数列の長さ,
　　　　　I:調べた数の最後の位置,V:先頭からIまでの要素数)
for/7->for(M:手前の数の長さ,K:次の数の最大長,J:探索する数の長さ,
　　　　　　L:入力値を数字のリスト化したもの,N:入力値の文字数,
　　　　　　I:調べた数の最後の位置,V:先頭からIまでの要素数)
prolog_flagで最大値(MAX)の保存変更をしています。(できれば使いたくなかったのですが)

dp/5のnth1/3でI+1番目が0でなければfor/7を呼び出し、Jを数列の次の要素の桁数とし、
J==MでI-M+1番目からのM桁の要素よりI+1番目からのM桁の要素が大きいとき(check1/5)、
およびJがM+1からKまでの間dp(L,N,J,I+J,V+1)を実行します。
I==Nとなったら、VとMAXの大きいほうをMAXとします。
ただし、MAXV-V>(N-I) div Jの時は枝刈します(for/7の二番目)。

disp/3のコメントアウトしている方が本来の問題用のコードです。
ただし本来の問題はideoneでは試せません。　

```Prolog
%SWI-Prolog version 7.4.2,7.6.4  
%:-initialization(start).    %ideone
%start

check1(_,_,_,0,0).
check1(L,A,B,M,R):-
     A1 is A+1,B1 is B+1,nth1(A1,L,V1),nth1(B1,L,V2),M1 is M-1,
     (V1>V2->R=0;(V1<V2->R=1;check1(L,A1,B1,M1,R))).

dp(_,N,_,I,V):-
     I=:=N,current_prolog_flag(count,MAX),MAX<V,set_prolog_flag(count,V).
dp(L,N,M,I,V):-
    I1 is I+1,nth1(I1,L,X),((X=\=0,K is N-I+1,K>M)->for(M,K,M,L,N,I,V);true).

for(_,K,K,_,_,_,_).
for(_,_,J,_,N,I,V):-
     J =\=0,(current_prolog_flag(count,MAX),X is MAX-V,Y is (N-I) div J,X>=Y),!.
for(M,K,J,L,N,I,V):-
     X is I-M,Y is I+M,Z is I+J,V1 is V+1,
     (M=:=J->(check1(L,X,I,M,B),(B=:=1->dp(L,N,M,Y,V1);true));dp(L,N,J,Z,V1)),
     J1 is J+1,for(M,K,J1,L,N,I,V).

solv8(S,R):-
     number_chars(S,L),maplist(atom_number,L,L1),length(L1,N),
     set_prolog_flag(count,0),dp(L1,N,0,0,0),current_prolog_flag(count,R),!.

start:-
     str(S),split_string(S,"\n","",S1),pre(S1),!.

pre([]).
pre([S|T]):-
     split_string(S,"\s","",[A,B,C]),number_chars(B1,B),solv8(B1,R),disp(R,C,A),pre(T).

%disp(R,Q,A):-number_string(N1,Q),(N1 =:= R->true;write(A:" ")).
%結果　14: 159: 265: 358: 979:

disp(R,Q,_):-number_string(N1,Q),(N1 =:= R->Str="pass ";Str="fail "),write(Str),writeln(R).

str("0 23342020662 4
1 23342121662 5
2 2334200200662 5
3 1 1
4 123 3
5 321 2
6 11 1
7 111 2
8 1111 2
9 223043 3
10 33616382 4
11 43727677 4
12 123456789 9
13 987654321 3
14 9876543210 4
15 1023456789 5
16 2000010000 1
17 1000020000 2
18 9080706050 2
19 1222222221 4
20 1222222223 5
21 5463728191 5
22 223138576279	6
23 9119291321331341 6
24 123456789101112131415 15
25 103456789101112131415 7
26 100000000000000000000123456789123456789123456789 2").
```
このようなプログラムをお見せしておいてなんですが、
Juliaでprologより早いプログラムを書こうといろいろ試した過程で気が付いたのですが、
正解は「狭義単調増加列」となる分け方の内、最後の数~~列~~が最小になるもののようです。
証明はできませんが、数字の数がn個で、A,B二つの分け方があって
Aの最後の数~~列~~がBの最後の数~~列~~より小さいときi番目で数列の境界が一致したとすると、
nからiまでのAの数列の数>=Bの数列の数にすることができ、
~~その次の数列もAの数列の大きさ=<Bの数列の大きさにできるので~~、
それ以降も
Aの数列の数をBの数列の数以上にできると思われます。
少なくともこの問題のデータの範囲では当てはまります。
つまり普通のメモ化再帰で最後の数~~列~~の小さい方から調べていき
結果が正になったところで終了です。（main()のif maxv>0 break end）
そのように書いたのが下のコードです。

dp(m,i)はi-m+1番目からi番目までのm桁の数を要素として持つ数列の内、
i番目までの要素数が一番多くなる場合の要素数vです。
数列の最後の要素の桁数をm=1からm=nまで増やしながら、dp(m,n)を求めます。
①前からm-i+1番目の数字(s2[i-m+1])が0ならdp(m,i)=mini
②v=dp(m-1,i-1)とするとその最後の要素に数字を一つくわえたものがdp(m,i)=v
③i-2*m+2番目からi-m番目までの要素の数v=dp(m-1,i-m)とするとdp(m,i)=v+1(①と重複あり）
④v=dp(m,i-m)とすると、i-2*m+1番目からi-m番目までの要素よりi-m+1番目からi番目まで
　の要素の方が大きい時(check(i-2*m,i-m,m)==1)のみdp(m,i)=v+1
最大のvをdp(m,i)および辞書dic[(m,i)]の値とします。
dp(m,n)が正になったら終了です。

```Julia
#ver 1.4.1,1.7.3

str　=　"0 23342020662 4
1 23342121662 5
2 2334200200662 5
3 1 1
4 123 3
5 321 2
6 11 1
7 111 2
8 1111 2
9 223043 3
10 33616382 4
11 43727677 4
12 123456789 9
13 987654321 3
14 9876543210 4
15 1023456789 5
16 2000010000 1
17 1000020000 2
18 9080706050 2
19 1222222221 4
20 1222222223 5
21 5463728191 5
22 223138576279 6
23 9119291321331341 6
24 123456789101112131415 15
25 103456789101112131415 7
26 100000000000000000000123456789123456789123456789 2"

function check(m1,m2,m)
   for i in 1:m
      if s2[m1+i]>s2[m2+i]
          return 0
      elseif s2[m1+i]<s2[m2+i]
          return 1
      end
   end
   return 0
end
function dp(m,i)
   if  haskey(dic,(m,i))
      ret=dic[(m,i)]
   elseif s2[i-m+1]=='0'
      ret=dic[(m,i)]=mini
   else
      v=mini
      if m>1
          v=dp(m-1,i-1)
          if i-2*m+1>=0
              v=max(v,dp(m-1,i-m)+1)
          end
      end
      if i-2*m>=0
          if check(i-2*m,i-m,m)==1
              v=max(v,dp(m,i-m)+1)
          end
      end
      ret=dic[(m,i)]=v
      return ret
   end
 end
 function main()
   ar=[]
   str1=split(str,"\n")
   for s in str1
      s1=split(s," ")
      global s2=s1[2]
      global n=length(s2)
      empty!(dic)
      for i in 1:n
        dic[(i,i)]=1
      end
      maxv=mini
      for m in 1:n
         maxv=max(maxv,dp(m,n))
         if maxv>0
            break
         end
      end
      if string(maxv) != s1[3]
          push!(ar,s1[1])
      end
   end
      println(join(ar,","))
 end

dic=Dict()
const mini=-1000000
@time main()
```