結果

問題 No.252 "良問"(良問とは言っていない (2)
ユーザー gew1fw
提出日時 2025-06-12 21:38:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,595 bytes
コンパイル時間 164 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 96,672 KB
最終ジャッジ日時 2025-06-12 21:43:24
合計ジャッジ時間 6,607 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def minimal_changes(s):
    n = len(s)
    # Precompute all "good" intervals
    good_intervals = []
    for i in range(n - 3):
        if s[i:i+4] == 'good':
            good_intervals.append((i, i+3))
    # Sort by end
    good_intervals.sort(key=lambda x: x[1])
    # Compute change positions for "good"
    change_good = []
    last = -1
    for interval in good_intervals:
        start, end = interval
        if start > last:
            change_good.append(end)
            last = end
    # Precompute all "problem" intervals
    problem_intervals = []
    for i in range(n - 6):
        if s[i:i+7] == 'problem':
            problem_intervals.append((i, i+6))
    # Sort by end
    problem_intervals.sort(key=lambda x: x[1])
    # Compute change positions for "problem"
    change_problem = []
    last = -1
    for interval in problem_intervals:
        start, end = interval
        if start > last:
            change_problem.append(end)
            last = end
    # Precompute cost_good and cost_problem
    cost_good = [0] * n
    for i in range(n):
        if i + 3 >= n:
            cost_good[i] = float('inf')
        else:
            cnt = 0
            if s[i] != 'g': cnt +=1
            if s[i+1] != 'o': cnt +=1
            if s[i+2] != 'o': cnt +=1
            if s[i+3] != 'd': cnt +=1
            cost_good[i] = cnt
    cost_problem = [0] * n
    for i in range(n):
        if i + 6 >= n:
            cost_problem[i] = float('inf')
        else:
            cnt = 0
            if s[i] != 'p': cnt +=1
            if s[i+1] != 'r': cnt +=1
            if s[i+2] != 'o': cnt +=1
            if s[i+3] != 'b': cnt +=1
            if s[i+4] != 'l': cnt +=1
            if s[i+5] != 'e': cnt +=1
            if s[i+6] != 'm': cnt +=1
            cost_problem[i] = cnt
    # Precompute sorted change positions
    change_good_sorted = sorted(change_good)
    change_problem_sorted = sorted(change_problem)
    # Now, for each possible i and j, compute the total cost
    min_total = float('inf')
    for i in range(n):
        if i + 3 >= n:
            continue
        if cost_good[i] == float('inf'):
            continue
        # Number of changes to break "good" before i
        cnt_good = bisect.bisect_right(change_good_sorted, i-1)
        # Now, find j >= i+4
        for j in range(i+4, n):
            if j + 6 >= n:
                continue
            if cost_problem[j] == float('inf'):
                continue
            # Number of changes to break "problem" before j
            cnt_problem = bisect.bisect_right(change_problem_sorted, j-1)
            total = cost_good[i] + cnt_good + cost_problem[j] + cnt_problem
            if total < min_total:
                min_total = total
    if min_total == float('inf'):
        # Need to create both "good" and "problem" somewhere
        # Find any i and j where j >= i+4
        possible = False
        for i in range(n - 3):
            for j in range(i+4, n -6):
                possible = True
                break
            if possible:
                break
        if not possible:
            return 0 # Not possible, but constraints say |S| >=11, which should allow
        # So compute minimal cost
        min_total = float('inf')
        for i in range(n -3):
            if cost_good[i] == float('inf'):
                continue
            for j in range(i+4, n-6):
                if cost_problem[j] == float('inf'):
                    continue
                # Compute cnt_good and cnt_problem as 0, since we are changing to create them
                # But wait, no: the change_good and change_problem are computed based on original string
                # So in this case, the changes are to create "good" and "problem", but also to break any existing "good" or "problem" before i and j.
                # So, the approach is same as before.
                # So, the minimal is the same as above, but in some cases, it's possible that the minimal is found in the loops above.
                # But if the initial loops didn't find any, then we have to compute it.
                # However, the code above should have considered all i and j.
                # So perhaps the initial code is sufficient.
                # But in the sample input, the minimal is found in the loop.
        pass
    return min_total

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    T = int(data[0])
    idx = 1
    for _ in range(T):
        s = data[idx]
        idx +=1
        print(minimal_changes(s))

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