#810351 (PyPy3) No.515 典型LCP

提出ソース
結果

問題	No.515 典型LCP
ユーザー	vwxyz
提出日時	2022-10-23 19:29:20
言語	PyPy3 (7.3.15)
結果	AC
実行時間	792 ms / 1,000 ms
コード長	14,750 bytes
コンパイル時間	208 ms
コンパイル使用メモリ	82,600 KB
実行使用メモリ	120,292 KB
最終ジャッジ日時	2024-07-02 10:02:23
合計ジャッジ時間	7,308 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	792 ms 120,292 KB
testcase_01	AC	724 ms 120,164 KB
testcase_02	AC	355 ms 90,796 KB
testcase_03	AC	136 ms 88,928 KB
testcase_04	AC	141 ms 88,828 KB
testcase_05	AC	236 ms 89,720 KB
testcase_06	AC	266 ms 89,600 KB
testcase_07	AC	236 ms 89,484 KB
testcase_08	AC	304 ms 89,468 KB
testcase_09	AC	264 ms 90,496 KB
testcase_10	AC	284 ms 90,880 KB
testcase_11	AC	275 ms 91,248 KB
testcase_12	AC	274 ms 91,264 KB
testcase_13	AC	263 ms 90,260 KB
testcase_14	AC	186 ms 90,496 KB
testcase_15	AC	223 ms 89,600 KB
testcase_16	AC	224 ms 89,800 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write

def SA_IS(lst,compressed=False):
    N=len(lst)
    if not compressed:
        decomp=sorted(list(set(lst)))
        comp={x:i for i,x in enumerate(decomp)}
        lst=[comp[s]+1 for s in lst]+[0]
    else:
        lst=[s+1 for s in lst]+[0]

    def induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index=None):
        buckets_left=[[] for b in range(bucket_count)]
        buckets_right=[[] for b in range(bucket_count)]
        if sorted_LMS_index==None:
            for i in LMS:
                buckets_right[lst[i]].append(i)
        else:
            for i in sorted_LMS_index[::-1]:
                buckets_right[lst[LMS[i]]].append(LMS[i])
        for b in range(bucket_count):
            for i in buckets_left[b]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            for i in buckets_right[b][::-1]:
                if i and type[i-1]=="L":
                    buckets_left[lst[i-1]].append(i-1)
            buckets_right[b]=[]
        for b in range(bucket_count-1,-1,-1):
            for i in buckets_right[b]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
            for i in buckets_left[b][::-1]:
                if i and type[i-1]=="S":
                    buckets_right[lst[i-1]].append(i-1)
        suffix_array=[N]
        for b in range(1,bucket_count):
            suffix_array+=buckets_left[b]+buckets_right[b][::-1]
        return suffix_array
    
    stack=[]
    while N>=1:
        type=[None]*(N+1)
        type[N]="S"
        for i in range(N-1,-1,-1):
            if lst[i]<lst[i+1]:
                type[i]="S"
            elif lst[i]>lst[i+1]:
                type[i]="L"
            else:
                type[i]=type[i+1]
        LMS=[i for i in range(1,N) if type[i-1]=="L" and type[i]=="S"]+[N]
        bucket_count=max(lst)+1
        stack.append((N,lst,type,LMS,bucket_count))
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count)
        LMS_substring=[None]*(N+1)
        for i in range(len(LMS)-1):
            LMS_substring[LMS[i]]=lst[LMS[i]:LMS[i+1]]
        LMS_substring[N]=lst[N:N+1]
        num=0
        prev=[0]
        for i in suffix_array:
            if LMS_substring[i]!=None:
                if prev!=LMS_substring[i]:
                    prev=LMS_substring[i]
                    num+=1
                LMS_substring[i]=num
        lst=[LMS_substring[i] for i in LMS]
        N=len(lst)-1
    sorted_LMS_index=[0]
    for N,lst,type,LMS,bucket_count in stack[::-1]:
        suffix_array=induced_sort(N,lst,type,LMS,bucket_count,sorted_LMS_index)
        sorted_LMS_index=suffix_array
    suffix_array=suffix_array[1:]
    return suffix_array

class Rolling_Hash:
    def __init__(self,lst,base,mod):
        assert math.gcd(base,mod)==1
        self.len=len(lst)
        self.base=base
        self.mod=mod
        self.rolling_hash=[None]*(self.len+1)
        self.rolling_hash[0]=0
        x=1
        for i in range(1,self.len+1):
            self.rolling_hash[i]=self.rolling_hash[i-1]+x*lst[i-1]
            self.rolling_hash[i]%=self.mod
            x*=self.base
            x%=self.mod
        x=MOD(self.mod).Pow(x,-1)
        self.base_reverse=[None]*(self.len+1)
        self.base_reverse[self.len]=x
        for i in range(self.len-1,-1,-1):
            self.base_reverse[i]=self.base_reverse[i+1]*self.base%self.mod

    def __getitem__(self,i):
        if type(i)==int:
            a,b=i,i+1
        else:
            a,b=i.start,i.stop
            if a==None or a<-self.len:
                a=0
            elif self.len<=a:
                a=self.len
            elif a<0:
                a+=self.len
            if b==None or self.len<=b:
                b=self.len
            elif b<-self.len:
                b=0
            elif b<0:
                b+=self.len
        return (self.rolling_hash[b]-self.rolling_hash[a])*self.base_reverse[a]%self.mod

    def __len__(self):
        return self.len

def Extended_Euclid(n,m):
    stack=[]
    while m:
        stack.append((n,m))
        n,m=m,n%m
    if n>=0:
        x,y=1,0
    else:
        x,y=-1,0
    for i in range(len(stack)-1,-1,-1):
        n,m=stack[i]
        x,y=y,x-(n//m)*y
    return x,y

class MOD:
    def __init__(self,p,e=None):
        self.p=p
        self.e=e
        if self.e==None:
            self.mod=self.p
        else:
            self.mod=self.p**self.e

    def Pow(self,a,n):
        a%=self.mod
        if n>=0:
            return pow(a,n,self.mod)
        else:
            assert math.gcd(a,self.mod)==1
            x=Extended_Euclid(a,self.mod)[0]
            return pow(x,-n,self.mod)

    def Build_Fact(self,N):
        assert N>=0
        self.factorial=[1]
        if self.e==None:
            for i in range(1,N+1):
                self.factorial.append(self.factorial[-1]*i%self.mod)
        else:
            self.cnt=[0]*(N+1)
            for i in range(1,N+1):
                self.cnt[i]=self.cnt[i-1]
                ii=i
                while ii%self.p==0:
                    ii//=self.p
                    self.cnt[i]+=1
                self.factorial.append(self.factorial[-1]*ii%self.mod)
        self.factorial_inve=[None]*(N+1)
        self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)
        for i in range(N-1,-1,-1):
            ii=i+1
            while ii%self.p==0:
                ii//=self.p
            self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod

    def Fact(self,N):
        if N<0:
            return 0
        retu=self.factorial[N]
        if self.e!=None and self.cnt[N]:
            retu*=pow(self.p,self.cnt[N],self.mod)%self.mod
            retu%=self.mod
        return retu

    def Fact_Inve(self,N):
        if self.e!=None and self.cnt[N]:
            return None
        return self.factorial_inve[N]

    def Comb(self,N,K,divisible_count=False):
        if K<0 or K>N:
            return 0
        retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.mod
        if self.e!=None:
            cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]
            if divisible_count:
                return retu,cnt
            else:
                retu*=pow(self.p,cnt,self.mod)
                retu%=self.mod
        return retu

def Bisect_Int(ok,ng,is_ok):
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if is_ok(mid):
            ok=mid
        else:
            ng=mid
    return ok

class Segment_Tree:
    def __init__(self,N,f,e,lst=None,dynamic=False):
        self.f=f
        self.e=e
        self.N=N
        if dynamic:
            self.segment_tree=defaultdict(lambda:self.e)
        else:
            if lst==None:
                self.segment_tree=[self.e]*2*self.N
            else:
                assert len(lst)<=self.N
                self.segment_tree=[self.e]*self.N+[x for x in lst]+[self.e]*(N-len(lst))
                for i in range(self.N-1,0,-1):
                    self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def __getitem__(self,i):
        if type(i)==int:
            if -self.N<=i<0:
                return self.segment_tree[i+self.N*2]
            elif 0<=i<self.N:
                return self.segment_tree[i+self.N]
            else:
                raise IndexError("list index out of range")
        else:
            a,b,c=i.start,i.stop,i.step
            if a==None:
                a=self.N
            else:
                a+=self.N
            if b==None:
                b=self.N*2
            else:
                b+=self.N
            return self.segment_tree[slice(a,b,c)]

    def __setitem__(self,i,x):
        if -self.N<=i<0:
            i+=self.N*2
        elif 0<=i<self.N:
            i+=self.N
        else:
            raise IndexError("list index out of range")
        self.segment_tree[i]=x
        while i>1:
            i>>= 1
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Build(self,lst):
        for i,x in enumerate(lst,self.N):
            self.segment_tree[i]=x
        for i in range(self.N-1,0,-1):
            self.segment_tree[i]=self.f(self.segment_tree[i<<1],self.segment_tree[i<<1|1])

    def Fold(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        vL=self.e
        vR=self.e
        while L<R:
            if L&1:
                vL=self.f(vL,self.segment_tree[L])
                L+=1
            if R&1:
                R-=1
                vR=self.f(self.segment_tree[R],vR)
            L>>=1
            R>>=1
        return self.f(vL,vR)

    def Fold_Index(self,L=None,R=None):
        if L==None:
            L=self.N
        else:
            L+=self.N
        if R==None:
            R=self.N*2
        else:
            R+=self.N
        if L==R:
            return None
        x=self.Fold(L-self.N,R-self.N)
        while L<R:
            if L&1:
                if self.segment_tree[L]==x:
                    i=L
                    break
                L+=1
            if R&1:
                R-=1
                if self.segment_tree[R]==x:
                    i=R
                    break
            L>>=1
            R>>=1
        while i<self.N:
            if self.segment_tree[i]==self.segment_tree[i<<1]:
                i<<=1
            else:
                i<<=1
                i|=1
        i-=self.N
        return i

    def Bisect_Right(self,L=None,f=None):
        if L==self.N:
            return self.N
        if L==None:
            L=0
        L+=self.N
        vl=self.e
        vr=self.e
        l,r=L,self.N*2
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return self.N
        v=self.e
        while True:
            while L%2==0:
                L>>=1
            vv=self.f(v,self.segment_tree[L])
            if f(vv):
                v=vv
                L+=1
            else:
                while L<self.N:
                    L<<=1
                    vv=self.f(v,self.segment_tree[L])
                    if f(vv):
                        v=vv
                        L+=1
                return L-self.N

    def Bisect_Left(self,R=None,f=None):
        if R==0:
            return 0
        if R==None:
            R=self.N
        R+=self.N
        vl=self.e
        vr=self.e
        l,r=self.N,R
        while l<r:
            if l&1:
                vl=self.f(vl,self.segment_tree[l])
                l+=1
            if r&1:
                r-=1
                vr=self.f(self.segment_tree[r],vr)
            l>>=1
            r>>=1
        if f(self.f(vl,vr)):
            return 0
        v=self.e
        while True:
            R-=1
            while R>1 and R%2:
                R>>=1
            vv=self.f(self.segment_tree[R],v)
            if f(vv):
                v=vv
            else:
                while R<self.N:
                    R=2*R+1
                    vv=self.f(self.segment_tree[R],v)
                    if f(vv):
                        v=vv
                        R-=1
                return R+1-self.N

    def __str__(self):
        return "["+", ".join(map(str,self.segment_tree[self.N:]))+"]"

class Path_Doubling:
    def __init__(self,N,permutation,lst=None,f=None,e=None):
        self.N=N
        self.permutation=permutation
        self.lst=lst
        self.f=f
        self.e=e

    def Build_Next(self,K=None):
        if K==None:
            K=self.N
        self.k=K.bit_length()
        self.permutation_doubling=[[self.permutation[n]] for n in range(self.N)]
        if self.lst!=None:
            self.doubling=[[self.lst[n]] for n in range(self.N)]
        for i in range(1,self.k):
            for n in range(self.N):
                self.permutation_doubling[n].append(self.permutation_doubling[self.permutation_doubling[n][i-1]][i-1])
                if self.f!=None:
                    self.doubling[n].append(self.f(self.doubling[n][i-1],self.doubling[self.permutation_doubling[n][i-1]][i-1]))

    def Permutation_Doubling(self,N,K):
        if K<0:
            return N
        for i in range(self.k):
            if K>>i&1:
                N=self.permutation_doubling[N][i]
        return N

    def Doubling(self,N,K):
        if K<0:
            return self.e
        retu=self.e
        for i in range(self.k):
            if K>>i&1:
                retu=self.f(retu,self.doubling[N][i])
                N=self.permutation_doubling[N][i]
        return retu

class Sparse_Table:
    def __init__(self,N,f,e,lst):
        self.N=N
        self.f=f
        self.e=e
        self.n=N.bit_length()
        self.dp=[[None]*(self.N-(1<<n)+1) for n in range(self.n)]
        if self.n:
            for i in range(self.N):
                self.dp[0][i]=lst[i]
            for n in range(1,self.n):
                for i in range(self.N-(1<<n)+1):
                    self.dp[n][i]=self.f(self.dp[n-1][i],self.dp[n-1][i+(1<<n-1)])

    def Fold(self,L,R):
        n=(R-L).bit_length()-1

from operator import itemgetter
N=int(readline())
S=[readline().rstrip() for n in range(N)]
S=sorted(list(enumerate(S)),key=itemgetter(1))
idx=[None]*N
for i in range(N):
    idx[S[i][0]]=i
    S[i]=S[i][1]
base=random.randint(1<<50,1<<51)
mod=(1<<61)-1
LCP=[0]*(N-1)
for i in range(N-1):
    for a,b in zip(S[i],S[i+1]):
        if a==b:
            LCP[i]+=1
        else:
            break
ans=0
inf=1<<30
LCP=Sparse_Table(N-1,min,inf,LCP)
M,x,d=map(int,readline().split())
for k in range(1,M+1):
    i,j=(x//(N-1)),(x%(N-1))
    if i>j:
        i,j=j,i
    else:
        j+=1
    x=(x+d)%(N*(N-1))
    i,j=idx[i],idx[j]
    if i>j:
        i,j=j,i
    n=(j-i).bit_length()-1
    ans+=min(LCP.dp[n][i],LCP.dp[n][j-(1<<n)])
print(ans)
yukicoder

結果

テストケース

ソースコード
