結果

問題 No.1055 牛歩
ユーザー qwewe
提出日時 2025-05-14 13:08:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 6,858 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,212 KB
実行使用メモリ 709,592 KB
最終ジャッジ日時 2025-05-14 13:09:36
合計ジャッジ時間 5,162 ms
ジャッジサーバーID
(参考情報)
judge4 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 5
other MLE * 1 -- * 69
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys

def solve():
    # Read N (number of squares) and M (number of pieces)
    N, M = map(int, sys.stdin.readline().split())
    
    # Read initial positions A_1, ..., A_M
    # The input guarantees A are sorted and distinct: 1 <= A_1 < A_2 < ... < A_M <= N
    A = list(map(int, sys.stdin.readline().split()))
    
    # Read Q (number of instructions)
    # Use readline().strip() to handle potential empty line or extra whitespace. Check if it's empty.
    q_line = sys.stdin.readline().strip()
    if not q_line:
        Q = 0
    else:
        try:
            Q = int(q_line)
        except ValueError:
            # Handle case where Q line might be invalid, though problem statement implies valid integer input
            # Based on constraints, Q >= 1 if B is provided. If Q=0, B won't be provided.
             # Let's assume valid input per problem statement structure. Minimal Q is likely 1 if B list exists.
             # The provided sample inputs always have Q >= 1 with a B list.
             # For safety against weird inputs, let's default to 0 if conversion fails and B is empty.
             # If B has content, Q must be > 0. Let's rely on input format guarantee.
             Q = int(q_line)


    # If Q is 0, no moves are required, so it's always possible.
    if Q == 0:
        print("YES")
        return
        
    # Read the sequence of piece indices B_1, ..., B_Q to be moved
    B = list(map(int, sys.stdin.readline().split()))

    # Set to store reachable states. A state is represented as a tuple of piece positions (p_1, ..., p_M).
    # Using a tuple makes the state hashable and usable in a set.
    # Initialize the set with the starting state.
    current_states = {tuple(A)}

    # Process each instruction B_k from k=0 to Q-1
    for k in range(Q):
        # Get the index of the piece to move (1-based index as per problem statement)
        piece_idx_1based = B[k]
        # Convert to 0-based index for list access (Python lists are 0-indexed)
        piece_idx_0based = piece_idx_1based - 1
        
        # Set to store states reachable after this k-th move
        next_states = set()
        
        # If there are no current states reachable, it's impossible to continue.
        # This condition means from all states reachable before step k, none allow a valid move for piece B[k].
        if not current_states:
             print("NO")
             return

        # Iterate through all currently reachable states
        for state in current_states:
            # Convert the tuple state back to a list to potentially modify positions.
            # `p` will hold the positions [p_1, ..., p_M] for the current state `state`.
            p = list(state) 
            current_pos = p[piece_idx_0based] # Position of the piece to be moved

            # --- Check left move possibility ---
            # Calculate the target position if moved left
            target_pos_L = current_pos - 1
            
            # Check boundary condition: target position must be at least 1.
            if target_pos_L >= 1: 
                # Collision check: 
                # If it's the first piece (piece 1, index 0), there's no piece to its left. Only boundary check matters.
                # If it's not the first piece, check if moving left would collide with its left neighbor (piece piece_idx_1based - 1).
                # The left neighbor is at index piece_idx_0based - 1.
                # The new position target_pos_L must be strictly greater than the left neighbor's position p[piece_idx_0based - 1]
                # to maintain the relative order p_1 < p_2 < ... < p_M.
                # This uses Python's short-circuit evaluation: if piece_idx_1based == 1, the second condition is not checked.
                if piece_idx_1based == 1 or target_pos_L > p[piece_idx_0based - 1]:
                    # If the move is valid (within bounds and no collision), calculate the new state.
                    # Create a copy of the current positions list
                    new_p_L = list(p)
                    # Update the position of the moved piece
                    new_p_L[piece_idx_0based] = target_pos_L
                    # Add the resulting state (as a tuple) to the set of next possible states.
                    next_states.add(tuple(new_p_L))

            # --- Check right move possibility ---
            # Calculate the target position if moved right
            target_pos_R = current_pos + 1

            # Check boundary condition: target position must be at most N.
            if target_pos_R <= N: 
                 # Collision check:
                 # If it's the last piece (piece M, index M-1), there's no piece to its right. Only boundary check matters.
                 # If it's not the last piece, check if moving right would collide with its right neighbor (piece piece_idx_1based + 1).
                 # The right neighbor is at index piece_idx_0based + 1.
                 # The new position target_pos_R must be strictly less than the right neighbor's position p[piece_idx_0based + 1].
                 # Uses short-circuit evaluation: if piece_idx_1based == M, the second condition is not checked.
                 if piece_idx_1based == M or target_pos_R < p[piece_idx_0based + 1]:
                     # If the move is valid, calculate the new state.
                     # Create a copy of the current positions list
                     new_p_R = list(p)
                     # Update the position of the moved piece
                     new_p_R[piece_idx_0based] = target_pos_R
                     # Add the resulting state (as a tuple) to the set of next possible states.
                     next_states.add(tuple(new_p_R))

        # After checking all possible moves from all current states, update the set of current states for the next iteration.
        current_states = next_states
        
        # If after processing moves for step k, the set of next_states is empty,
        # it means no valid move could be made for piece B[k] from any state reachable at step k-1.
        # Therefore, it's impossible to follow the instructions. Print NO and exit.
        # This check is implicitly handled by the 'if not current_states:' check at the beginning of the next loop iteration.
        # Adding an explicit check here is also fine.
        if not current_states:
            print("NO")
            return

    # If the loop completes successfully for all Q instructions:
    # It means that for every instruction k, there was at least one state reachable at step k-1
    # from which piece B[k] could make a valid move.
    # And after the Q-th instruction, the set current_states is non-empty.
    # Therefore, it is possible to follow all instructions.
    print("YES")

# Call the solve function to execute the logic
solve()
0