結果

問題 No.2332 Make a Sequence
ユーザー navel_tosnavel_tos
提出日時 2023-11-05 19:30:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 7,713 bytes
コンパイル時間 623 ms
コンパイル使用メモリ 81,884 KB
実行使用メモリ 218,440 KB
最終ジャッジ日時 2023-11-05 19:31:21
合計ジャッジ時間 51,565 ms
ジャッジサーバーID
(参考情報)
judge15 / judge13
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,684 KB
testcase_01 AC 39 ms
53,684 KB
testcase_02 AC 40 ms
53,684 KB
testcase_03 AC 39 ms
53,684 KB
testcase_04 AC 40 ms
53,684 KB
testcase_05 AC 39 ms
53,684 KB
testcase_06 AC 39 ms
53,684 KB
testcase_07 AC 409 ms
199,788 KB
testcase_08 AC 159 ms
103,516 KB
testcase_09 AC 244 ms
153,940 KB
testcase_10 AC 298 ms
174,052 KB
testcase_11 AC 215 ms
157,452 KB
testcase_12 AC 414 ms
218,204 KB
testcase_13 AC 356 ms
218,436 KB
testcase_14 AC 349 ms
218,440 KB
testcase_15 AC 375 ms
218,440 KB
testcase_16 AC 351 ms
218,436 KB
testcase_17 AC 380 ms
218,436 KB
testcase_18 AC 347 ms
218,436 KB
testcase_19 AC 355 ms
218,436 KB
testcase_20 AC 349 ms
218,440 KB
testcase_21 AC 349 ms
218,440 KB
testcase_22 AC 425 ms
217,120 KB
testcase_23 AC 401 ms
216,980 KB
testcase_24 AC 415 ms
217,384 KB
testcase_25 AC 393 ms
217,120 KB
testcase_26 AC 407 ms
217,724 KB
testcase_27 AC 455 ms
216,220 KB
testcase_28 AC 435 ms
217,648 KB
testcase_29 AC 437 ms
216,588 KB
testcase_30 AC 480 ms
216,588 KB
testcase_31 AC 482 ms
216,232 KB
testcase_32 AC 521 ms
215,008 KB
testcase_33 AC 509 ms
216,332 KB
testcase_34 AC 559 ms
215,268 KB
testcase_35 AC 545 ms
216,068 KB
testcase_36 AC 554 ms
216,328 KB
testcase_37 AC 588 ms
198,748 KB
testcase_38 AC 630 ms
214,780 KB
testcase_39 AC 679 ms
214,788 KB
testcase_40 AC 558 ms
205,696 KB
testcase_41 AC 568 ms
214,744 KB
testcase_42 AC 1,122 ms
176,304 KB
testcase_43 AC 1,093 ms
176,308 KB
testcase_44 AC 1,004 ms
197,160 KB
testcase_45 AC 1,052 ms
177,652 KB
testcase_46 AC 1,141 ms
197,160 KB
testcase_47 TLE -
testcase_48 TLE -
testcase_49 TLE -
testcase_50 TLE -
testcase_51 TLE -
testcase_52 AC 435 ms
215,856 KB
testcase_53 AC 473 ms
216,044 KB
testcase_54 AC 424 ms
216,056 KB
testcase_55 AC 483 ms
215,968 KB
testcase_56 AC 468 ms
217,068 KB
testcase_57 AC 443 ms
217,656 KB
testcase_58 AC 440 ms
216,620 KB
testcase_59 AC 400 ms
217,472 KB
testcase_60 AC 449 ms
217,124 KB
testcase_61 AC 510 ms
216,688 KB
testcase_62 AC 1,663 ms
210,292 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#MMA Contest 015 K Make a Sequence

'''
L問題はSegTreeを頑張ったら独力ACできたので、これが実質ラスボス。

■設問
連続部分列A[:k]を足すことをくり返し、列Bを作れ。コストは k*C(len(B))だけかかるので最安で。


■考察
ぜんぜんわからん。DPみは感じる。
ロリハするなり単純比較するなりで遷移はできるけど、実質O(N^2) むりでは


■解説
Li Chao Tree。なんだそれ。
EDPC - Z で@kyopro_friendsさんがやってたアルゴリズム、でいいのか?

操作前依存ならEDPC-Zを振り返るシリーズになるが、
今回は単調性が操作前にあるから、遷移がうまくいかない。

わからん。一晩考えよう。

蟻本式(?)deque型CHTをSegTreeに載せれば線分クエリは解けるが、
そもそも傾きの単調性が担保されないので

Li-Chao Segment Treeを履修しないとだめですか
だめですね やります


■Rolling Hash
RHを整備してから見直したら入力は整数
文字列対応版しか作っていませんが?わろた 作り直します
作り直しました


■Li Chao Tree
ABC244ExのKiri8128さんの答案から窃取
いつもありがとうございます
Reference: https://atcoder.jp/contests/abc244/editorial/3626

区間クエリ対応を手動で行ったので壊れているかも
あと元のライブラリが多倍長整数上等なやつなのでTLEするかも
やばそう


■提出
TLE6(?) これは仕方ない、infを10^50から10^18へ丸める暴挙に出ます
→TLE5 わろた Z-algorithmでやります
'''
#Z-algorithm  TとS[i:]のLCP判定は、T+'$'+S のようにSに出ない文字を挟んで実行するとよい
#Reference: https://tjkendev.github.io/procon-library/python/string/z-algorithm.html
def Z_algorithm(S):  #SとS[i:]の最長共通接頭辞を求める
    N=len(S); A=[0]*N; i,j=1,0; A[0]=L=N
    while i<L:
        while i+j<L and S[j]==S[i+j]: j+=1
        if not j: i+=1; continue
        A[i]=j; k=1
        while L-i>k<j-A[k]: A[i+k]=A[k]; k+=1
        i+=k; j-=k
    return A


#Rolling Hash: 2^61-1 の原始根: r=37  基数はM-1と互いに素、かつ r^k(mod M)>max(A)を推奨
class Rolling_Hash:
    def __init__(self,Base=128,MOD=2**61-1): self._B=Base; self._MOD=MOD; self._Bf=[1]
    def _translate(self,String):
        return [ord(String[i]) for i in range(len(String))] if isinstance(String,str) else String
    def _factorial(self,N):  #B^iを前計算する
        Start=len(self._Bf)
        while len(self._Bf)<=N: self._Bf+=[0]*len(self._Bf)
        for i in range(Start,len(self._Bf)): self._Bf[i]=self._Bf[i-1]*self._B%self._MOD
    def hash(self,Sequence):
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        self._factorial(len(Sequence))
        return sum(Sequence[i]*self._Bf[len(Sequence)-i-1]%self._MOD
                   for i in range(len(Sequence)))%self._MOD
    def rolling(self,Sequence,Len):
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        if len(Sequence)<=Len: return [self.hash(Sequence)]
        L=[0]*(len(Sequence)-Len+1); L[0]=self.hash(Sequence[:Len])
        for i in range(len(Sequence)-Len):
            L[i+1]=L[i]*self._B-Sequence[i]*self._Bf[Len]+Sequence[i+Len]
            if L[i+1]>=self._MOD: L[i+1]%=self._MOD
        return L

    #ここからQuick Rolling Hash  文字列前登録の元、O(1)でハッシュ値を返す
    def build(self,Sequence):  #文字列を受入れ
        if isinstance(Sequence,str): Sequence=self._translate(Sequence)
        self._S=Sequence; self._N=len(self._S); self._factorial(self._N); self._H=[0]*(self._N+1)
        for i in range(self._N): self._H[i]=(self._H[i-1]*self._B+self._S[i])%self._MOD
        return
    def Qhash(self,L,R):  #S[L,R)のハッシュ値を返す
        return (self._H[R-1]-self._H[L-1]*self._Bf[R-L])%self._MOD if L<R<=self._N else 0


#Li Chao Tree: 直線/線分追加、地点minを処理  線分はO(log^2(N))
#Reference: https://atcoder.jp/contests/abc244/submissions/30307939
#Reference: https://smijake3.hatenablog.com/entry/2018/06/16/144548
class Li_Chao_Tree:
    def __init__(self,XList):  #調べる可能性のあるX座標リストを渡す
        XList=sorted(set(XList)); self._inf=10**18; self._N=1<<(len(XList)-1).bit_length()
        self._X=XList+[self._inf]*(self._N-len(XList)); XList.append(self._inf)
        self._D={x:i for i,x in enumerate(XList)}
        self._LMR=[(0,0,0)]*self._N+[(x,x,x) for x in self._X]
        for i in range(self._N-1,0,-1):
            self._LMR[i]=(self._LMR[i*2][0],self._LMR[i*2][2],self._LMR[i*2+1][2])
        self._F=[None]*2*self._N
    def _line(self,f,x): return f[0]*x+f[1]
    def _update_all(self,i,f):  #全域更新版
        while 1:
            L,M,R=self._LMR[i]; Fi=self._F[i]
            if Fi==None: self._F[i]=f; Fi=self._F[i]; return
            cL,cR=(Fi[0]-f[0])*L +Fi[1]-f[1]>0, (Fi[0]-f[0])*R +Fi[1]-f[1]>0
            if cL*cR: self._F[i]=f; return  #both True:  最強なので更新して終了
            if not cL and not cR:   return  #both False: 捨てて終了
            if (Fi[0]-f[0])*M +Fi[1]-f[1]>0: self._F[i]=f; f=Fi; cL=not cL
            i=i*2 if cL else i*2+1
    def _update_seg(self,i,f,qL,qR):  #区間更新版 [qL,qR)に対して更新する
        qR=self._X[self._D[qR]]  #ノードは閉区間 なので更新範囲も閉区間に修正
        while 1:
            L,M,R=self._LMR[i]; Fi=self._F[i]
            if R<qL or qR<L: return  #区間[qL,qR]を含まない
            if not (qL<=L and R<=qR):  #区間[qL,qR]を半端に含む
                self._update_seg(i*2,f,qL,qR); self._update_seg(i*2+1,f,qL,qR); return
            if Fi==None: self._F[i]=f; Fi=self._F[i]
            cL,cR=(Fi[0]-f[0])*L +Fi[1]-f[1]>0, (Fi[0]-f[0])*R +Fi[1]-f[1]>0
            if cL*cR: self._F[i]=f; return
            if not cL and not cR:   return
            if (Fi[0]-f[0])*M +Fi[1]-f[1]>0: self._F[i]=f; f=Fi; cL=not cL
            i=i*2 if cL else i*2+1
    def add_line(self,a,b): self._update_all(1,(a,b))  #直線 y=ax+b を追加
    def add_lineseg(self,a,b,xL=None,xR=None):         #線分を追加
        xL=-self._inf if xL==None else xL; xR=self._inf if xR==None else xR
        if xL>=xR: return
        self._update_seg(1,(a,b),xL,xR)
    def query(self,x):  #最小値クエリに回答する
        i=self._D[x]+self._N; Mi=self._inf
        while i>0:
            if self._F[i]: Mi=min(Mi,self._line(self._F[i],x))
            i>>=1
        return Mi


f=lambda:list(map(int,input().split()))

#入力受取
N,M=f(); A=f(); B=f(); C=f()

#Z-algorithmでLCPを計算 O(N)
LCP=Z_algorithm(A+[-1]+B)[-M:]

'''
#Rolling Hashと二分探索で最長共通接頭辞を計算 O(NlogN)
RHA=Rolling_Hash(37**6); RHA.build(A)
RHB=Rolling_Hash(37**6); RHB.build(B); LCP=[0]*M
for Lt in range(M):
    AC,WA=Lt,min(M,Lt+N)+1
    while abs(AC-WA)>1:  #ハッシュの衝突対策で、最終結果提出前に検算を行う
        while abs(AC-WA)>1:
            WJ=(AC+WA)//2; AC,WA=(WJ,WA) if RHA.Qhash(0,WJ-Lt)==RHB.Qhash(Lt,WJ) else (AC,WJ)
        WJ=(Lt+AC)//2; AC,WA=(AC,WA) if RHA.Qhash(0,WJ-Lt)==RHB.Qhash(Lt,WJ) else (Lt,AC)
    LCP[Lt]=AC-Lt
'''
    
#Li Chao Tree: 線分・直線追加クエリに対する最小値をO(log^2(N))で求める
#DP[i]: i-1文字目を入力しきる文字数
LCT=Li_Chao_Tree([i for i in range(M+1)])
DP=[0]*M; LCT.add_lineseg(C[0],0,0,LCP[0])

#クエリを実行
for i in range(1,M): DP[i]=LCT.query(i); LCT.add_lineseg(C[i],DP[i]-C[i]*i,i,i+LCP[i])
print(LCT.query(M)) if LCT.query(M)<10**18 else print(-1)
0