結果
問題 | No.2332 Make a Sequence |
ユーザー | navel_tos |
提出日時 | 2023-11-05 19:30:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,713 bytes |
コンパイル時間 | 343 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 219,056 KB |
最終ジャッジ日時 | 2024-09-25 22:40:17 |
合計ジャッジ時間 | 45,785 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
53,632 KB |
testcase_01 | AC | 44 ms
53,376 KB |
testcase_02 | AC | 48 ms
53,376 KB |
testcase_03 | AC | 42 ms
53,248 KB |
testcase_04 | AC | 42 ms
52,992 KB |
testcase_05 | AC | 43 ms
53,376 KB |
testcase_06 | AC | 42 ms
53,376 KB |
testcase_07 | AC | 350 ms
200,352 KB |
testcase_08 | AC | 117 ms
103,552 KB |
testcase_09 | AC | 262 ms
154,176 KB |
testcase_10 | AC | 313 ms
174,468 KB |
testcase_11 | AC | 264 ms
158,008 KB |
testcase_12 | AC | 407 ms
218,668 KB |
testcase_13 | AC | 383 ms
218,792 KB |
testcase_14 | AC | 371 ms
218,788 KB |
testcase_15 | AC | 380 ms
218,796 KB |
testcase_16 | AC | 375 ms
218,788 KB |
testcase_17 | AC | 403 ms
219,052 KB |
testcase_18 | AC | 372 ms
219,056 KB |
testcase_19 | AC | 375 ms
218,784 KB |
testcase_20 | AC | 367 ms
218,708 KB |
testcase_21 | AC | 370 ms
218,660 KB |
testcase_22 | AC | 414 ms
217,520 KB |
testcase_23 | AC | 417 ms
217,448 KB |
testcase_24 | AC | 421 ms
217,768 KB |
testcase_25 | AC | 396 ms
217,516 KB |
testcase_26 | AC | 419 ms
218,240 KB |
testcase_27 | AC | 454 ms
216,716 KB |
testcase_28 | AC | 451 ms
218,156 KB |
testcase_29 | AC | 446 ms
216,992 KB |
testcase_30 | AC | 455 ms
216,984 KB |
testcase_31 | AC | 493 ms
216,848 KB |
testcase_32 | AC | 529 ms
215,464 KB |
testcase_33 | AC | 528 ms
216,624 KB |
testcase_34 | AC | 572 ms
215,584 KB |
testcase_35 | AC | 531 ms
216,612 KB |
testcase_36 | AC | 561 ms
216,620 KB |
testcase_37 | AC | 569 ms
199,244 KB |
testcase_38 | AC | 634 ms
214,860 KB |
testcase_39 | AC | 712 ms
215,252 KB |
testcase_40 | AC | 606 ms
206,296 KB |
testcase_41 | AC | 597 ms
215,076 KB |
testcase_42 | AC | 1,136 ms
176,592 KB |
testcase_43 | AC | 1,046 ms
176,592 KB |
testcase_44 | AC | 1,015 ms
197,456 KB |
testcase_45 | AC | 1,015 ms
178,156 KB |
testcase_46 | AC | 1,192 ms
197,712 KB |
testcase_47 | TLE | - |
testcase_48 | TLE | - |
testcase_49 | TLE | - |
testcase_50 | TLE | - |
testcase_51 | TLE | - |
testcase_52 | AC | 445 ms
216,428 KB |
testcase_53 | AC | 458 ms
216,720 KB |
testcase_54 | AC | 435 ms
216,608 KB |
testcase_55 | AC | 476 ms
216,332 KB |
testcase_56 | AC | 473 ms
217,596 KB |
testcase_57 | AC | 454 ms
218,060 KB |
testcase_58 | AC | 451 ms
217,040 KB |
testcase_59 | AC | 458 ms
217,864 KB |
testcase_60 | AC | 479 ms
217,652 KB |
testcase_61 | AC | 597 ms
216,980 KB |
testcase_62 | AC | 1,645 ms
210,768 KB |
ソースコード
#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)