結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー qwewe
提出日時 2025-04-24 12:30:59
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,614 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 194,048 KB
最終ジャッジ日時 2025-04-24 12:32:32
合計ジャッジ時間 4,027 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 1 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    
    for S in cases:
        lenS = len(S)
        first_good = None
        first_problem = None
        
        # Find first occurrence of "good"
        for i in range(lenS - 3):
            if S[i] == 'g' and S[i+1] == 'o' and S[i+2] == 'o' and S[i+3] == 'd':
                first_good = i
                break
        
        # Find first occurrence of "problem"
        for i in range(lenS - 6):
            if S[i] == 'p' and S[i+1] == 'r' and S[i+2] == 'o' and S[i+3] == 'b' and S[i+4] == 'l' and S[i+5] == 'e' and S[i+6] == 'm':
                first_problem = i
                break
        
        if first_good is not None and first_problem is not None and first_good < first_problem:
            print(0)
            continue
        
        # Precompute cost_good and cost_problem
        cost_good = []
        good_starts = []
        for i in range(lenS - 3):
            cost = 0
            if S[i] != 'g':
                cost +=1
            if S[i+1] != 'o':
                cost +=1
            if S[i+2] != 'o':
                cost +=1
            if S[i+3] != 'd':
                cost +=1
            cost_good.append(cost)
            if cost == 0:
                good_starts.append(i)
        
        cost_problem = []
        problem_starts = []
        for j in range(lenS - 6):
            cost = 0
            if S[j] != 'p':
                cost +=1
            if S[j+1] != 'r':
                cost +=1
            if S[j+2] != 'o':
                cost +=1
            if S[j+3] != 'b':
                cost +=1
            if S[j+4] != 'l':
                cost +=1
            if S[j+5] != 'e':
                cost +=1
            if S[j+6] != 'm':
                cost +=1
            cost_problem.append(cost)
            if cost == 0:
                problem_starts.append(j)
        
        # Sort the starts lists
        good_starts.sort()
        problem_starts.sort()
        
        # Precompute problem_cost and min_suffix
        len_problem = len(cost_problem)
        problem_cost = []
        for j in range(len_problem):
            threshold = j - 6
            cnt = bisect.bisect_left(problem_starts, threshold)
            pc = cost_problem[j] + cnt
            problem_cost.append(pc)
        
        # Create min_suffix
        min_suffix = [float('inf')] * (len_problem + 1)  # padding at the end
        if len_problem > 0:
            min_suffix[len_problem - 1] = problem_cost[len_problem - 1]
            for j in range(len_problem - 2, -1, -1):
                min_suffix[j] = min(problem_cost[j], min_suffix[j+1])
        else:
            min_suffix = [float('inf')]
        
        min_total = float('inf')
        len_good = len(cost_good)
        for i in range(len_good):
            threshold = i - 3
            cnt_good = bisect.bisect_left(good_starts, threshold)
            j_min = i + 4
            if j_min > len_problem - 1:
                continue
            current_min = min_suffix[j_min]
            total = cost_good[i] + cnt_good + current_min
            if total < min_total:
                min_total = total
        
        if min_total == float('inf'):
            # Check if there's any possible j after i without the j >= i+4 constraint
            # But according to problem statement, |S| >=11, so there must be a solution
            # So this case should not happen
            print(-1)
        else:
            print(min_total)

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