結果
| 問題 | No.2332 Make a Sequence |
| ユーザー |
 navel_tos
|
| 提出日時 | 2023-06-01 19:38:18 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,713 bytes |
| コンパイル時間 | 322 ms |
| コンパイル使用メモリ | 86,948 KB |
| 実行使用メモリ | 219,672 KB |
| 最終ジャッジ日時 | 2023-08-28 02:09:34 |
| 合計ジャッジ時間 | 43,751 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 70 ms
71,244 KB |
| testcase_01 | AC | 73 ms
71,136 KB |
| testcase_02 | AC | 70 ms
71,252 KB |
| testcase_03 | AC | 69 ms
71,328 KB |
| testcase_04 | AC | 73 ms
71,092 KB |
| testcase_05 | AC | 73 ms
71,312 KB |
| testcase_06 | AC | 73 ms
71,312 KB |
| testcase_07 | AC | 342 ms
200,544 KB |
| testcase_08 | AC | 141 ms
104,660 KB |
| testcase_09 | AC | 261 ms
162,152 KB |
| testcase_10 | AC | 331 ms
184,452 KB |
| testcase_11 | AC | 236 ms
158,684 KB |
| testcase_12 | AC | 398 ms
219,256 KB |
| testcase_13 | AC | 366 ms
219,328 KB |
| testcase_14 | AC | 360 ms
219,352 KB |
| testcase_15 | AC | 362 ms
219,616 KB |
| testcase_16 | AC | 361 ms
219,664 KB |
| testcase_17 | AC | 393 ms
219,672 KB |
| testcase_18 | AC | 364 ms
219,532 KB |
| testcase_19 | AC | 367 ms
219,184 KB |
| testcase_20 | AC | 364 ms
219,492 KB |
| testcase_21 | AC | 363 ms
219,620 KB |
| testcase_22 | AC | 416 ms
217,760 KB |
| testcase_23 | AC | 419 ms
218,024 KB |
| testcase_24 | AC | 435 ms
218,728 KB |
| testcase_25 | AC | 401 ms
218,156 KB |
| testcase_26 | AC | 422 ms
218,420 KB |
| testcase_27 | AC | 458 ms
218,220 KB |
| testcase_28 | AC | 461 ms
218,836 KB |
| testcase_29 | AC | 456 ms
218,432 KB |
| testcase_30 | AC | 468 ms
217,900 KB |
| testcase_31 | AC | 500 ms
217,572 KB |
| testcase_32 | AC | 512 ms
196,832 KB |
| testcase_33 | AC | 508 ms
200,356 KB |
| testcase_34 | AC | 567 ms
200,076 KB |
| testcase_35 | AC | 524 ms
198,016 KB |
| testcase_36 | AC | 557 ms
200,156 KB |
| testcase_37 | AC | 569 ms
180,884 KB |
| testcase_38 | AC | 630 ms
191,976 KB |
| testcase_39 | AC | 647 ms
190,908 KB |
| testcase_40 | AC | 561 ms
182,836 KB |
| testcase_41 | AC | 533 ms
193,144 KB |
| testcase_42 | AC | 1,101 ms
199,728 KB |
| testcase_43 | AC | 1,080 ms
205,888 KB |
| testcase_44 | AC | 1,022 ms
204,432 KB |
| testcase_45 | AC | 1,049 ms
200,820 KB |
| testcase_46 | AC | 1,087 ms
204,252 KB |
| testcase_47 | TLE | - |
| testcase_48 | TLE | - |
| testcase_49 | TLE | - |
| testcase_50 | TLE | - |
| testcase_51 | TLE | - |
| testcase_52 | AC | 443 ms
208,028 KB |
| testcase_53 | AC | 466 ms
210,368 KB |
| testcase_54 | AC | 439 ms
210,588 KB |
| testcase_55 | AC | 469 ms
207,692 KB |
| testcase_56 | AC | 485 ms
208,732 KB |
| testcase_57 | AC | 458 ms
218,756 KB |
| testcase_58 | AC | 454 ms
217,188 KB |
| testcase_59 | AC | 413 ms
218,368 KB |
| testcase_60 | AC | 467 ms
208,684 KB |
| testcase_61 | AC | 511 ms
208,016 KB |
| testcase_62 | AC | 1,613 ms
189,432 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)