結果

問題 No.3110 Like CPCTF?
コンテスト
ユーザー FP1uto
提出日時 2025-04-19 04:31:58
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 4,933 bytes
コンパイル時間 565 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2025-04-19 04:32:01
合計ジャッジ時間 2,205 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 3
other RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect
from collections import defaultdict
S=int(input())
N=input()

def solve(S,N):
    # S = input().strip()
    # N = len(S)
    pos = defaultdict(list)
    for i, c in enumerate(S):
        pos[c].append(i)
    
    # Precompute for each k: count_left_equal[k], left_unique[k], right_unique[k]
    count_left_equal = [0] * N
    left_unique = [0] * N  # number of unique characters to the left of k (excluding S[k])
    right_unique = [0] * N  # number of unique characters to the right of k (excluding S[k])
    
    # Compute count_left_equal and left_unique
    freq_left = defaultdict(int)
    unique_left = 0
    for k in range(N):
        c = S[k]
        count_left_equal[k] = bisect.bisect_left(pos[c], k)
        # Update left_unique: number of unique characters before k (excluding c)
        left_unique[k] = len(freq_left) - (1 if c in freq_left else 0)
        freq_left[c] += 1
    
    # Compute right_unique
    freq_right = defaultdict(int)
    for k in range(N-1, -1, -1):
        c = S[k]
        right_unique[k] = len(freq_right) - (1 if c in freq_right else 0)
        freq_right[c] += 1
    
    total = 0
    for k in range(2, N-2):  # 3rd character is at index k (0-based)
        c = S[k]
        L = left_unique[k]
        R = right_unique[k]
        # Number of ways to choose 2nd character: L
        # Number of ways to choose 4th and 5th characters: R choose 2, but ensuring they are different from 2nd
        # Since 2nd is chosen from left_unique, which excludes c, and right_unique also excludes c,
        # the only overlap is if the 2nd character is in the right_unique set.
        # So the number of valid (d, e) pairs is R choose 2 minus the number of pairs where one is the 2nd character.
        # But since we don't know the 2nd character yet, this is tricky.
        # Alternative approach: for each possible 2nd character (from left_unique), compute the number of valid (d, e) in right.
        # But this would be O(26) per k.
        # Instead, precompute for each k, the set of left_unique characters and their counts.
        pass
    
    # More precise approach:
    # For each k, the 2nd character can be any character in left_unique[k] (excluding c).
    # Then, the 4th and 5th characters must be different from c and from each other, and also from the 2nd character.
    # So for each k:
    # total += count_left_equal[k] * sum_{d in left_unique[k]} (number of (e, f) in right_unique[k] where e != f and e != d and f != d)
    # This seems complex, but can be simplified by noting that:
    # sum_{d} [ (R - cnt[d in right]) choose 2 ]
    # where cnt[d in right] is 1 if d is in right_unique[k], else 0.
    
    # So we need for each k:
    # left_chars = set of characters to the left of k (excluding c)
    # right_chars = set of characters to the right of k (excluding c)
    # overlap = left_chars & right_chars
    # For each d in left_chars:
    #   if d in right_chars:
    #       available_right = R - 1
    #   else:
    #       available_right = R
    #   total += count_left_equal[k] * (available_right choose 2)
    # But since count_left_equal[k] is the same for all d, we can factor it out:
    # total += count_left_equal[k] * sum_{d in left_chars} ( (R - (1 if d in right_chars else 0)) choose 2 )
    
    # To compute this efficiently, we need for each k:
    # left_chars: the set of unique characters to the left of k (excluding c)
    # right_chars: the set of unique characters to the right of k (excluding c)
    # Then, the sum is:
    # (number of d in left_chars not in right_chars) * (R choose 2) + (number of d in left_chars in right_chars) * ((R-1) choose 2)
    
    # So, for each k:
    # left_only = left_unique[k] - len(left_chars & right_chars)
    # both = len(left_chars & right_chars)
    # total += count_left_equal[k] * (left_only * R*(R-1)//2 + both * (R-1)*(R-2)//2)
    
    # Now, how to compute left_chars and right_chars for each k?
    # We can precompute for each k, the set of characters to the left (excluding c) and to the right (excluding c).
    
    # Precompute left_chars and right_chars for each k
    left_chars = [set() for _ in range(N)]
    current_left = set()
    for k in range(N):
        c = S[k]
        left_chars[k] = current_left.copy()
        current_left.add(c)
    
    right_chars = [set() for _ in range(N)]
    current_right = set()
    for k in range(N-1, -1, -1):
        c = S[k]
        right_chars[k] = current_right.copy()
        current_right.add(c)
    
    total = 0
    for k in range(2, N-2):
        c = S[k]
        left_set = left_chars[k]
        right_set = right_chars[k]
        overlap = left_set & right_set
        left_only = len(left_set) - len(overlap)
        both = len(overlap)
        R = len(right_set)
        term = left_only * R * (R - 1) // 2 + both * (R - 1) * (R - 2) // 2
        total += count_left_equal[k] * term
    
    print(total)

solve(S,N)
0