結果

問題 No.295 hel__world
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:00:42
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,703 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 81,824 KB
実行使用メモリ 83,208 KB
最終ジャッジ日時 2025-04-16 16:04:27
合計ジャッジ時間 7,753 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 10 WA * 1 TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
from collections import defaultdict

def main():
    S = list(map(int, input().split()))
    T = input().strip()
    
    # Split T into runs
    runs = []
    if not T:
        print(0)
        return
    current_char = T[0]
    current_length = 1
    for c in T[1:]:
        if c == current_char:
            current_length += 1
        else:
            runs.append((current_char, current_length))
            current_char = c
            current_length = 1
    runs.append((current_char, current_length))
    
    # Check if the number of runs for each character is <= S[alpha]
    run_counts = defaultdict(int)
    for c, _ in runs:
        idx = ord(c) - ord('a')
        if S[idx] == 0:
            print(0)
            return
        run_counts[c] += 1
    
    for c in run_counts:
        idx = ord(c) - ord('a')
        if run_counts[c] > S[idx]:
            print(0)
            return
    
    # Check sum of t_i for each character
    sum_t = defaultdict(int)
    for c, t in runs:
        sum_t[c] += t
    
    for c in sum_t:
        idx = ord(c) - ord('a')
        if sum_t[c] > S[idx]:
            print(0)
            return
    
    # Now, compute the product
    product = 1
    MAX = 2 ** 62
    
    # Group runs by character
    char_runs = defaultdict(list)
    for c, t in runs:
        char_runs[c].append(t)
    
    for c in char_runs:
        idx = ord(c) - ord('a')
        sum_t_c = sum(char_runs[c])
        rem_c = S[idx] - sum_t_c
        if rem_c < 0:
            print(0)
            return
        if rem_c == 0:
            for t in char_runs[c]:
                product *= 1
                if product >= MAX:
                    print("hel")
                    return
            continue
        
        # Need to allocate rem_c to the runs of this character
        runs_t = char_runs[c]
        m = len(runs_t)
        heap = []
        for i in range(m):
            t_i = runs_t[i]
            # Initial gain is (t_i + 0 + 1) / (0 + 1) = t_i + 1
            # Use negative for min-heap
            heapq.heappush(heap, (-(t_i + 1.0), 0, i))
        
        k_list = [0] * m
        
        for _ in range(rem_c):
            neg_gain, current_k, i = heapq.heappop(heap)
            current_gain = -neg_gain
            # Allocate one more to this run
            new_k = current_k + 1
            t_i = runs_t[i]
            new_gain = (t_i + new_k) / (new_k)
            heapq.heappush(heap, (-new_gain, new_k, i))
            k_list[i] = new_k
        
        # Now compute the product for each run
        for i in range(m):
            t_i = runs_t[i]
            k_i = k_list[i]
            s_i = t_i + k_i
            # Compute C(s_i, t_i)
            comb = 1
            numerator = s_i
            denominator = t_i
            if denominator > numerator:
                comb = 0
            else:
                # Compute product from s_i - t_i + 1 to s_i, divided by t_i!
                # But to avoid large computations, compute incrementally and check overflow
                # We can compute it as product_{1..t_i} (s_i - t_i + j) / j
                # Wait, C(s_i, t_i) = product_{j=1 to t_i} (s_i - t_i + j) / j
                # Which is the same as product_{j=1 to t_i} (k_i + j) / j
                # Because s_i = t_i + k_i
                for j in range(1, t_i + 1):
                    comb *= (k_i + j)
                    comb //= j
                    if comb >= MAX:
                        print("hel")
                        return
            product *= comb
            if product >= MAX:
                print("hel")
                return
    
    print(product)

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