結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー qwewe
提出日時 2025-05-14 13:23:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,451 bytes
コンパイル時間 367 ms
コンパイル使用メモリ 82,060 KB
実行使用メモリ 97,064 KB
最終ジャッジ日時 2025-05-14 13:25:14
合計ジャッジ時間 6,781 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def solve():
    S = input()
    n = len(S)
    
    patterns = ["good", "problem"]
    pattern_masks = [1, 2] # 1 for "good", 2 for "problem"

    # Build Aho-Corasick automaton
    # Max states roughly sum of lengths of patterns + 1
    # good (4), problem (7) -> 4+7+1 = 12 states initially.
    # Let's allocate a bit more just in case, e.g., 20.
    MAX_AC_STATES = sum(len(p) for p in patterns) + 5 
    
    trie = [[0] * 26 for _ in range(MAX_AC_STATES)]
    # output_at_state[ac_state] stores the bitmask of patterns ending at this state
    output_at_state = [0] * MAX_AC_STATES
    failure_link = [0] * MAX_AC_STATES # failure_link[ac_state] is the state to go to on failure
    
    num_ac_states = 1 # state 0 is the root (empty string)

    for p_idx, p_str in enumerate(patterns):
        curr_node = 0
        for char_val in p_str:
            char_code = ord(char_val) - ord('a')
            if trie[curr_node][char_code] == 0:
                trie[curr_node][char_code] = num_ac_states
                num_ac_states += 1
            curr_node = trie[curr_node][char_code]
        output_at_state[curr_node] |= pattern_masks[p_idx]

    # Build failure links using BFS
    queue = []
    for char_code in range(26):
        if trie[0][char_code] != 0: # Children of root
            queue.append(trie[0][char_code])
            # failure_link for children of root is root itself (0)

    head = 0
    while head < len(queue):
        u_node = queue[head]
        head += 1

        # For each character, find transition from u_node
        for char_code in range(26):
            v_node = trie[u_node][char_code]
            if v_node == 0: # No direct child with this char
                continue

            # v_node is a direct child of u_node
            # To find failure_link[v_node]:
            # Start from failure_link[u_node] and try to follow char_code
            f_u = failure_link[u_node]
            while f_u != 0 and trie[f_u][char_code] == 0:
                f_u = failure_link[f_u]
            
            failure_link[v_node] = trie[f_u][char_code]
            # Important: Output of a state includes outputs of its failure state
            output_at_state[v_node] |= output_at_state[failure_link[v_node]]
            
            queue.append(v_node)

    # Precompute goto function for AC (memoized transitions)
    # ac_goto[state][char_code] = next_state
    ac_goto_memo = [[-1] * 26 for _ in range(num_ac_states)]

    def get_ac_next_state(curr_ac_state, char_code):
        if ac_goto_memo[curr_ac_state][char_code] != -1:
            return ac_goto_memo[curr_ac_state][char_code]
        
        temp_state = curr_ac_state
        while temp_state != 0 and trie[temp_state][char_code] == 0:
            temp_state = failure_link[temp_state]
        
        res_state = trie[temp_state][char_code]
        ac_goto_memo[curr_ac_state][char_code] = res_state
        return res_state

    # DP state: dp[ac_state][phase] = min_cost
    # Phases:
    # 0: Before finding "good"
    # 1: After "good" found, before "problem" (that's after "good")
    # 2: After "good" and then "problem" both found
    dp = [[math.inf] * 3 for _ in range(num_ac_states)]
    dp[0][0] = 0 # Start at root (state 0), phase 0, cost 0

    for k in range(n): # Iterate through characters of S
        s_original_char_code = ord(S[k]) - ord('a')
        new_dp = [[math.inf] * 3 for _ in range(num_ac_states)]

        for prev_ac_state in range(num_ac_states):
            for prev_phase in range(3):
                if dp[prev_ac_state][prev_phase] == math.inf:
                    continue

                for char_code_to_place in range(26): # Try all 'a' through 'z'
                    cost_for_char = 0 if char_code_to_place == s_original_char_code else 1
                    
                    current_ac_state = get_ac_next_state(prev_ac_state, char_code_to_place)
                    matches = output_at_state[current_ac_state]
                    
                    current_phase = prev_phase
                    
                    # Update phase based on matches
                    # Order matters: if "good" matched, phase can go 0->1. Then if "problem" also matched, phase can go 1->2.
                    if (matches & pattern_masks[0]): # "good" matched
                        if current_phase == 0:
                            current_phase = 1
                    
                    if (matches & pattern_masks[1]): # "problem" matched
                        if current_phase == 0: # Problem found before good, or simultaneously but "good" didn't set phase to 1
                                               # This path is invalid.
                            continue # Skip updating dp for this invalid transition
                        elif current_phase == 1:
                            current_phase = 2
                    
                    new_dp[current_ac_state][current_phase] = min(
                        new_dp[current_ac_state][current_phase],
                        dp[prev_ac_state][prev_phase] + cost_for_char
                    )
        dp = new_dp

    min_total_cost = math.inf
    for final_ac_state in range(num_ac_states):
        min_total_cost = min(min_total_cost, dp[final_ac_state][2])
        
    return min_total_cost if min_total_cost != math.inf else -1 # Should always be possible

T = int(input())
for _ in range(T):
    print(solve())
0