結果

問題 No.515 典型LCP
ユーザー rpy3cpp
提出日時 2017-05-06 01:46:44
言語 PyPy3
(7.0.0)
結果
TLE  
実行時間 -
コード長 2,670 Byte
コンパイル時間 256 ms
使用メモリ 88,080 KB
最終ジャッジ日時 2020-01-26 06:49:14

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
challenge01.txt TLE -
challenge02.txt TLE -
challenge03.txt AC 412 ms
83,476 KB
sample1.txt AC 104 ms
78,392 KB
sample2.txt AC 108 ms
78,384 KB
testeasy0.txt AC 292 ms
82,820 KB
testeasy1.txt AC 288 ms
83,164 KB
testeasy2.txt AC 284 ms
83,428 KB
testeasy3.txt AC 356 ms
83,648 KB
testhard0.txt AC 300 ms
83,184 KB
testhard1.txt AC 344 ms
85,792 KB
testhard2.txt AC 348 ms
85,708 KB
testhard3.txt AC 348 ms
85,720 KB
testtough0.txt AC 284 ms
83,448 KB
testtough1.txt AC 176 ms
83,320 KB
testtough2.txt AC 256 ms
87,760 KB
testtough3.txt AC 284 ms
88,080 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