結果

問題 No.295 hel__world
ユーザー lam6er
提出日時 2025-03-20 20:53:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,767 bytes
コンパイル時間 184 ms
コンパイル使用メモリ 82,700 KB
実行使用メモリ 231,876 KB
最終ジャッジ日時 2025-03-20 20:53:19
合計ジャッジ時間 10,793 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 39 TLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    S_alpha = list(map(int, input().split()))
    T = input().strip()
    
    # Process T into runs
    runs = []
    if not T:
        print(0)
        return
    current_char = T[0]
    current_count = 1
    for c in T[1:]:
        if c == current_char:
            current_count += 1
        else:
            runs.append((current_char, current_count))
            current_char = c
            current_count = 1
    runs.append((current_char, current_count))
    
    # Check number of runs per character
    char_runs = {}
    for char, cnt in runs:
        char_runs.setdefault(char, []).append(cnt)
    
    # Check if number of runs is feasible for each character
    for char in char_runs:
        idx = ord(char) - ord('a')
        m_c = len(char_runs[char])
        if S_alpha[idx] < m_c:
            print(0)
            return
    
    # Check sum of t_i <= S_alpha for each character
    for char in char_runs:
        idx = ord(char) - ord('a')
        sum_t = sum(char_runs[char])
        if sum_t > S_alpha[idx]:
            print(0)
            return
    
    # Calculate the product of combinations
    overflow = 2 ** 62
    result = 1
    
    for char in char_runs:
        idx = ord(char) - ord('a')
        current_runs = char_runs[char]
        S_c = S_alpha[idx]
        sum_t = sum(current_runs)
        excess = S_c - sum_t
        
        product_c = 1
        
        # Check if all t_i are 1
        all_ones = all(ti == 1 for ti in current_runs)
        m_c = len(current_runs)
        
        if all_ones:
            # Maximize product of (e_i + 1)
            total = excess + m_c  # since sum (e_i + 1) = excess + m_c
            base = total // m_c
            remainder = total % m_c
            part = base
            comb = 1
            for _ in range(remainder):
                comb *= (part + 1)
                if comb > overflow:
                    print("hel")
                    return
            for _ in range(m_c - remainder):
                comb *= part
                if comb > overflow:
                    print("hel")
                    return
            product_c = comb
        else:
            # Use priority queue approach
            e_values = [0] * len(current_runs)
            heap = []
            for i, ti in enumerate(current_runs):
                e_i = e_values[i]
                gain = (ti + e_i + 1) / (e_i + 1)
                heapq.heappush(heap, (-gain, i))
            
            remaining = excess
            while remaining > 0 and heap:
                neg_gain, i = heapq.heappop(heap)
                ti = current_runs[i]
                e_i = e_values[i]
                
                e_values[i] += 1
                remaining -= 1
                
                new_gain = (ti + e_values[i] + 1) / (e_values[i] + 1)
                heapq.heappush(heap, (-new_gain, i))
            
            # Compute product for current character
            for i in range(len(current_runs)):
                ti = current_runs[i]
                e_i = e_values[i]
                total = ti + e_i
                # Compute combination C(total, ti)
                comb = 1
                numerator = 1
                denominator = 1
                for k in range(1, ti + 1):
                    numerator *= (e_i + k)
                    denominator *= k
                comb = numerator // denominator
                product_c *= comb
                if product_c >= overflow or product_c < 0:
                    print("hel")
                    return
        
        result *= product_c
        if result >= overflow or result < 0:
            print("hel")
            return
    
    print(result)

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