結果

問題 No.515 典型LCP
ユーザー rpy3cpp
提出日時 2017-05-06 01:46:44
言語 PyPy3
(7.0.0)
結果
TLE  
実行時間 -
コード長 2,670 Byte
コンパイル時間 251 ms
使用メモリ 77,012 KB
最終ジャッジ日時 2019-09-20 18:27:33

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt TLE -
challenge02.txt TLE -
challenge03.txt AC 413 ms
72,640 KB
sample1.txt AC 127 ms
67,340 KB
sample2.txt AC 126 ms
67,340 KB
testeasy0.txt AC 296 ms
72,096 KB
testeasy1.txt AC 303 ms
72,336 KB
testeasy2.txt AC 282 ms
72,388 KB
testeasy3.txt AC 344 ms
72,396 KB
testhard0.txt AC 293 ms
72,356 KB
testhard1.txt AC 341 ms
74,992 KB
testhard2.txt AC 346 ms
74,992 KB
testhard3.txt AC 356 ms
75,000 KB
testtough0.txt AC 305 ms
72,524 KB
testtough1.txt AC 191 ms
72,396 KB
testtough2.txt AC 263 ms
76,772 KB
testtough3.txt AC 289 ms
77,012 KB
テストケース一括ダウンロード

ソースコード

diff #
# -*- coding: utf-8 -*-
#import math

class RMQ(object):
    def __init__(self, A):
        self._A = A
        self._preprocess()

    def _preprocess(self):
        ''' RMQ の前処理。
        '''
        n = len(self._A)
        max_j = n.bit_length() - 1  # int(math.log2(n))
        self._M = [list(range(n))]
        for j in range(0, max_j):
            shift = 1 << j
            Mj = self._M[j]
            Mjnext = []
            for k1, k2 in zip(Mj, Mj[shift:]):
                k = k1 if self._A[k1] < self._A[k2] else k2
                Mjnext.append(k)
            self._M.append(Mjnext)

    def query(self, i, j):
        if i == j: return i
        if i > j: i, j = j, i
        el = (j - i).bit_length() - 1 # int(math.log2(j - i))
        k1 = self._M[el][i]
        k2 = self._M[el][j - (1 << el) + 1]
        rmq = k1 if self._A[k1] < self._A[k2] else k2
        return rmq

class LCP(object):
    '''Longest Common Prefix を計算するクラス
    lcp = LCP(lst_of_strings)
    lcp.get(i, j)
    '''
    def __init__(self, strings):
        strings_with_index = [(s, i) for i, s in enumerate(strings)]
        strings_with_index.sort()
        sorted_strings = []
        self._index_converter = [0] * len(strings)
        j = 0
        for s, i in strings_with_index:
            sorted_strings.append(s)
            self._index_converter[i] = j
            j += 1
        self._init_lcp_neighbours(sorted_strings)
        self._rmq = RMQ(self._lcp_neighbours)
        self._lens = list(map(len, sorted_strings))
            
    def _init_lcp_neighbours(self, ss):
        n = len(ss)
        self._lcp_neighbours = [self._calc_lcp(ss[i], ss[i + 1]) for i in range(n - 1)]

    def _calc_lcp(self, str0, str1):
        lcp = 0
        for c0, c1 in zip(str0, str1):
            if c0 != c1:
                return lcp
            else:
                lcp += 1
        return lcp
    
    def get(self, i, j):
        ''' strings[i] と strings[j] の LCP の長さを返す
        '''
        ii = self._index_converter[i]
        jj = self._index_converter[j]
        if ii == jj:
            return self._lens[ii]
        if ii > jj: ii, jj = jj, ii
        kk = self._rmq.query(ii, jj - 1)
        return self._lcp_neighbours[kk]


if __name__ == '__main__':
    N = int(input())
    strings = [input() for _ in range(N)]
    M, x, d = map(int, input().split())
    lcp = LCP(strings)
    Nm1 = N - 1
    NN = N * (N - 1)
    cum = 0
    for k in range(M):
        i, j = divmod(x, Nm1)
        if (i > j):
            i, j = j, i
        else:
            j += 1
        cum += lcp.get(i, j)
        x = (x + d) % NN
    print(cum)
0