結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー lam6er
提出日時 2025-04-09 21:01:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,509 bytes
コンパイル時間 497 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 83,272 KB
最終ジャッジ日時 2025-04-09 21:02:09
合計ジャッジ時間 9,613 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 TLE * 2 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    T = int(input[0])
    cases = input[1:T+1]
    GOOD = 'good'
    PROBLEM = 'problem'
    len_good = len(GOOD)
    len_problem = len(PROBLEM)
    
    for s in cases:
        n = len(s)
        # Precompute cost_g_part and cost_p_part
        cost_g_part = []
        for i in range(n - len_good + 1):
            cost = 0
            for j in range(len_good):
                if s[i + j] != GOOD[j]:
                    cost += 1
            cost_g_part.append(cost)
        
        cost_p_part = []
        for i in range(n - len_problem + 1):
            cost = 0
            for j in range(len_problem):
                if s[i + j] != PROBLEM[j]:
                    cost += 1
            cost_p_part.append(cost)
        
        # Precompute good_positions and problem_positions in original string
        good_positions = []
        for i in range(n - len_good + 1):
            if s[i:i+len_good] == GOOD:
                good_positions.append(i)
        
        problem_positions = []
        for i in range(n - len_problem + 1):
            if s[i:i+len_problem] == PROBLEM:
                problem_positions.append(i)
        
        # Precompute count_good_break for each i
        count_good_break = [0] * n
        for i in range(n):
            cnt = 0
            for k in good_positions:
                if k < i and (k + len_good - 1) < i:
                    cnt += 1
            count_good_break[i] = cnt
        
        # Precompute count_problem_break for each j
        count_problem_break = [0] * n
        for j in range(n):
            cnt = 0
            for k in problem_positions:
                if k < j and (k + len_problem - 1) < j:
                    cnt += 1
            count_problem_break[j] = cnt
        
        # Iterate all possible i and j to find the minimal cost
        min_cost = float('inf')
        max_good_i = n - len_good
        for i in range(max_good_i + 1):
            cost_g = cost_g_part[i]
            # j must be >= i + 4 and valid (j + 7 -1 <= n-1)
            min_j = i + 4
            max_j = n - len_problem
            if min_j > max_j:
                continue
            for j in range(min_j, max_j + 1):
                cost_p = cost_p_part[j]
                total = cost_g + cost_p + count_good_break[i] + count_problem_break[j]
                if total < min_cost:
                    min_cost = total
        print(min_cost)

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