結果

問題 No.2281 K → K-1 01 Flip
ユーザー qwewe
提出日時 2025-05-14 13:04:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 4,571 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 848,792 KB
最終ジャッジ日時 2025-05-14 13:05:53
合計ジャッジ時間 4,932 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other MLE * 1 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def solve():
    # Read N and Q from input
    N, Q = map(int, sys.stdin.readline().split())
    # Read the string S
    S = sys.stdin.readline().strip()
    
    # List to store results for each query
    results = []
    
    # Memoization dictionary to store results for (substring, K) pairs.
    # Key is a tuple (substring, K)
    # Value is the minimum length achievable.
    memo = {} 

    for query_idx in range(Q):
        # Read query parameters L, R, K
        L, R, K = map(int, sys.stdin.readline().split())
        
        # Extract the substring S[L-1...R-1] (0-based indexing)
        sub = S[L-1:R]
        
        # Create state key for memoization
        state_key = (sub, K)

        # Check if result for this state is already memoized
        if state_key in memo:
            results.append(memo[state_key])
            continue

        # Initialize BFS queue with the initial substring
        q = deque([sub]) 
        # Set to keep track of visited states (substrings) to avoid cycles and redundant processing
        visited_bfs = {sub}
        
        # Initialize minimum length found so far with the initial substring length
        min_len_found = len(sub)
        
        # Perform BFS to explore reachable states
        while q:
            # Get the current state (substring) from the front of the queue
            curr_s = q.popleft()
            
            # Update the minimum length found with the length of the current state
            min_len_found = min(min_len_found, len(curr_s))

            # Check if K is valid (problem statement guarantees K >= 2)
            if K <= 0: # Should not happen based on constraints K >= 2
                 continue 
            if K==1: # Should not happen based on constraints K >= 2
                 continue

            # Define the target patterns and their replacements
            target0 = '0' * K # Pattern of K zeros
            replace1 = '1' * (K - 1) # Replacement with K-1 ones
            
            target1 = '1' * K # Pattern of K ones
            replace0 = '0' * (K - 1) # Replacement with K-1 zeros

            # Find all occurrences of target0 (K zeros) and generate next states
            idx = 0
            while True:
                 # Find the next occurrence of target0 starting from index idx
                 found_idx = curr_s.find(target0, idx)
                 # If no more occurrences found, break the loop
                 if found_idx == -1: break
                 
                 # Generate the next state by replacing target0 with replace1
                 next_s = curr_s[:found_idx] + replace1 + curr_s[found_idx+K:]
                 
                 # If the generated state has not been visited
                 if next_s not in visited_bfs:
                     # Add it to the queue for processing
                     q.append(next_s)
                     # Mark it as visited
                     visited_bfs.add(next_s)
                 
                 # Continue searching for target0 from the position after the found occurrence
                 idx = found_idx + 1 

            # Find all occurrences of target1 (K ones) and generate next states
            idx = 0
            while True:
                 # Find the next occurrence of target1 starting from index idx
                 found_idx = curr_s.find(target1, idx)
                 # If no more occurrences found, break the loop
                 if found_idx == -1: break
                 
                 # Generate the next state by replacing target1 with replace0
                 next_s = curr_s[:found_idx] + replace0 + curr_s[found_idx+K:]
                 
                 # If the generated state has not been visited
                 if next_s not in visited_bfs:
                     # Add it to the queue for processing
                     q.append(next_s)
                     # Mark it as visited
                     visited_bfs.add(next_s)
                 
                 # Continue searching for target1 from the position after the found occurrence
                 idx = found_idx + 1
        
        # After BFS completes, min_len_found holds the minimum length among all reachable states
        # Store the result in the memoization table
        memo[state_key] = min_len_found
        # Add the result to the list of results
        results.append(min_len_found)

    # Print all results
    for res in results:
        sys.stdout.write(str(res) + '\n')

# Execute the solve function
solve()
0