結果

問題 No.962 LCPs
ユーザー lam6er
提出日時 2025-03-20 20:39:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 258 ms / 2,000 ms
コード長 4,957 bytes
コンパイル時間 200 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 143,164 KB
最終ジャッジ日時 2025-03-20 20:39:52
合計ジャッジ時間 8,228 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    S = data[1:N+1]
    len_list = [len(s) for s in S]
    
    if N == 0:
        print(0)
        return
    
    # Precompute LCP for consecutive pairs
    lcp_list = []
    for i in range(N-1):
        a = S[i]
        b = S[i+1]
        min_len = min(len(a), len(b))
        lcp = 0
        while lcp < min_len and a[lcp] == b[lcp]:
            lcp += 1
        lcp_list.append(lcp)
    
    events = []
    for i in range(N):
        events.append((-len_list[i], 'element', i))  # Use negative to reverse sort
    
    for i in range(N-1):
        events.append((-lcp_list[i], 'pair', i))
    
    # Sort events. For the same m, process elements before pairs to enable elements first
    events.sort()
    
    parent = list(range(N))
    left = list(range(N))
    right = list(range(N))
    enabled_elements = [False] * N
    enabled_pairs = [False] * (N-1)
    current_sum = 0
    answer = 0
    prev_m = None
    
    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u
    
    for event in events:
        m_neg, typ, idx = event
        m = -m_neg
        if prev_m is not None:
            delta = prev_m - m
            answer += current_sum * delta
        else:
            delta = 0
        prev_m = m
        
        if typ == 'element':
            i = idx
            if enabled_elements[i]:
                continue
            enabled_elements[i] = True
            K = 1
            contribute = K * (K + 1) * (K + 2) // 6
            current_sum += contribute
            
            # Check left neighbor
            if i > 0 and enabled_elements[i-1] and enabled_pairs[i-1]:
                left_root = find(i-1)
                current_root = find(i)
                if left_root != current_root:
                    left_left = left[left_root]
                    left_right = right[left_root]
                    current_left = left[current_root]
                    current_right = right[current_root]
                    if left_right + 1 == current_left:
                        K1 = left_right - left_left + 1
                        K2 = current_right - current_left + 1
                        current_sum -= K1 * (K1+1) * (K1+2) // 6
                        current_sum -= K2 * (K2+1) * (K2+2) // 6
                        parent[current_root] = left_root
                        left[left_root] = left_left
                        right[left_root] = current_right
                        new_K = right[left_root] - left[left_root] + 1
                        current_sum += new_K * (new_K + 1) * (new_K + 2) // 6
            # Check right neighbor
            if i < N-1 and enabled_elements[i+1] and enabled_pairs[i]:
                right_root = find(i+1)
                current_root = find(i)
                if right_root != current_root:
                    current_left = left[current_root]
                    current_right = right[current_root]
                    right_left = left[right_root]
                    right_right = right[right_root]
                    if current_right + 1 == right_left:
                        K1 = current_right - current_left + 1
                        K2 = right_right - right_left + 1
                        current_sum -= K1 * (K1+1) * (K1+2) // 6
                        current_sum -= K2 * (K2+1) * (K2+2) // 6
                        parent[right_root] = current_root
                        right[current_root] = right_right
                        new_K = right[current_root] - left[current_root] + 1
                        current_sum += new_K * (new_K + 1) * (new_K + 2) // 6
        else:
            # pair event
            i = idx
            if enabled_pairs[i]:
                continue
            enabled_pairs[i] = True
            if enabled_elements[i] and enabled_elements[i+1]:
                # Try to merge the segments
                root1 = find(i)
                root2 = find(i+1)
                if root1 == root2:
                    continue
                left1 = left[root1]
                right1 = right[root1]
                left2 = left[root2]
                right2 = right[root2]
                if right1 + 1 == left2:
                    K1 = right1 - left1 + 1
                    K2 = right2 - left2 + 1
                    current_sum -= K1 * (K1+1) * (K1+2) //6
                    current_sum -= K2 * (K2+1) * (K2+2) //6
                    parent[root2] = root1
                    left[root1] = left1
                    right[root1] = right2
                    new_K = right[root1] - left[root1] +1
                    current_sum += new_K * (new_K+1) * (new_K+2) //6
    # Add remaining m=prev_m down to 0
    if prev_m is not None:
        answer += current_sum * prev_m
    
    print(answer)

if __name__ == '__main__':
    main()
0