結果

問題 No.2738 CPC To F
ユーザー qwewe
提出日時 2025-05-14 13:11:01
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 4,421 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,976 KB
実行使用メモリ 94,336 KB
最終ジャッジ日時 2025-05-14 13:12:55
合計ジャッジ時間 1,957 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    # Read the integer N, the length of the string.
    N = int(sys.stdin.readline())
    # Read the string S.
    S = sys.stdin.readline().strip()

    # Initialize a list to store the intervals corresponding to potential "CPCTF" occurrences.
    # Each interval will be stored as a tuple (start_index, end_index).
    intervals = []

    # Define the first target pattern: "CPCTF" (length 5).
    # This pattern can exist in the original string.
    target1 = "CPCTF"
    len1 = 5
    
    # Use str.find() to efficiently find all occurrences of target1.
    # str.find(substring, start_pos) returns the lowest index where substring is found,
    # at or after start_pos. Returns -1 if not found.
    current_pos = 0 # Start searching from index 0.
    while True:
        # Find the index of the next occurrence of target1 starting from current_pos.
        idx = S.find(target1, current_pos)
        # If find returns -1, it means no more occurrences are found. Break the loop.
        if idx == -1:
            break
        # If an occurrence is found at index 'idx', add the corresponding interval [idx, idx + len1 - 1] to the list.
        # The interval represents the range of indices in the original string S occupied by this occurrence.
        intervals.append((idx, idx + len1 - 1))
        # Update current_pos to idx + 1 to continue searching for the next occurrence.
        # Starting the next search from idx + 1 allows finding overlapping occurrences if necessary,
        # although the greedy selection later ensures non-overlapping final choices.
        current_pos = idx + 1 

    # Define the second target pattern: "CPCTCPC" (length 7).
    # This pattern represents a sequence that can be transformed into "CPCTF"
    # by applying the operation "CPC" -> "F" on the suffix "CPC".
    target2 = "CPCTCPC"
    len2 = 7
    
    # Find all occurrences of target2 using str.find().
    current_pos = 0 # Reset search position for the second pattern.
    while True:
        # Find the index of the next occurrence of target2 starting from current_pos.
        idx = S.find(target2, current_pos)
        # If find returns -1, break the loop.
        if idx == -1:
            break
        # If an occurrence is found at index 'idx', add the corresponding interval [idx, idx + len2 - 1] to the list.
        # This interval represents the range of indices in the original string S occupied by this potential source of "CPCTF".
        intervals.append((idx, idx + len2 - 1))
        # Update current_pos for the next search.
        current_pos = idx + 1

    # The problem asks for the maximum number of non-overlapping "CPCTF" occurrences.
    # We have identified all potential sources (original "CPCTF" and "CPCTCPC").
    # Each source corresponds to an interval in the original string S.
    # We need to select a maximum number of these intervals such that no two selected intervals overlap.
    # This is a classic interval scheduling problem (specifically, activity selection).
    # The standard greedy approach works: sort intervals by their end points and pick greedily.
    
    # Sort the intervals based on their end points (ascending).
    # If end points are equal, use start points (ascending) as a tie-breaker. This secondary sort key is not strictly necessary but is standard practice.
    intervals.sort(key=lambda x: (x[1], x[0]))

    count = 0 # Initialize the count of selected non-overlapping intervals.
    last_end = -1 # Initialize the end index of the last selected interval. Set to -1 initially (effectively negative infinity).

    # Iterate through the sorted intervals.
    for s, e in intervals:
        # Check if the current interval's start index `s` is greater than `last_end`.
        # This condition ensures that the current interval starts *after* the previously selected interval ends.
        # Hence, they are non-overlapping. Indices are inclusive, so if interval A ends at index `e`, the next interval B must start at index `s > e`.
        if s > last_end:
            # If the current interval is non-overlapping with the previously selected one, select it.
            count += 1 # Increment the count of selected intervals.
            last_end = e # Update `last_end` to the end index of the currently selected interval.

    # Print the final maximum count.
    print(count)

# Execute the main solver function.
solve()
0