結果

問題 No.3066 Collecting Coins Speedrun 1
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:18:13
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 6,575 bytes
コンパイル時間 330 ms
コンパイル使用メモリ 82,776 KB
実行使用メモリ 72,600 KB
最終ジャッジ日時 2025-05-14 13:19:03
合計ジャッジ時間 3,996 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Increase recursion depth for potentially deep calls in calculate_grundy.
# The required depth depends on PRECOMPUTE_LIMIT. A value like 200 should be safe.
try:
    # Increase recursion depth for deep calculations during precomputation.
    # The actual depth needed depends on the structure of recursive calls.
    # Since calculate_grundy(L) depends on smaller values, max depth is roughly L.
    sys.setrecursionlimit(200) 
except Exception as e:
    # Some environments might restrict changing recursion depth.
    # If so, we rely on the default limit. Memoization helps prune redundant calls.
    # print(f"Could not set recursion depth: {e}", file=sys.stderr)
    pass

# Memoization dictionary stores computed Grundy numbers
memo = {}

# Periodicity information determined from analyzing the Grundy sequence
PERIOD = 68
PERIOD_START_IDX = 34
# Precompute Grundy numbers up to the point where periodicity is established plus one full period length.
# This ensures any L >= PERIOD_START_IDX can rely on values within the range [PERIOD_START_IDX, PERIOD_START_IDX + PERIOD - 1]
# PRECOMPUTE_LIMIT = PERIOD_START_IDX + PERIOD = 34 + 68 = 102. We compute values G[0]...G[101].
PRECOMPUTE_LIMIT = PERIOD_START_IDX + PERIOD 


def calculate_grundy(L):
    """ Calculates the Grundy number for a segment of length L using memoization and periodicity. """
    
    # Base case: segment of length 0 or less has Grundy value 0.
    if L <= 0: 
        return 0
    
    # Check memo first: if already computed, return stored value.
    if L in memo:
        return memo[L]

    # Apply periodicity for large L values.
    # If L is large enough such that its equivalent L based on periodicity must fall
    # within the precomputed range [0, PRECOMPUTE_LIMIT - 1], we compute its value recursively.
    if L >= PERIOD_START_IDX:
        # Calculate the equivalent L within the first periodic block
        # The equivalent index range is [PERIOD_START_IDX, PERIOD_START_IDX + PERIOD - 1]
        equivalent_L = PERIOD_START_IDX + (L - PERIOD_START_IDX) % PERIOD
        
        # If L itself is outside the precomputation range, its value is determined solely by periodicity.
        # The value for equivalent_L is guaranteed to be in memo after the precomputation loop finishes.
        if L >= PRECOMPUTE_LIMIT: 
             res = memo[equivalent_L] 
             # Store the result for L as well, potentially optimizing future calls if L is queried again.
             memo[L] = res 
             return res
        # If L is within the precomputed range [PERIOD_START_IDX, PRECOMPUTE_LIMIT - 1],
        # we proceed to compute it normally. The computation might recursively call calculate_grundy
        # for values potentially determined by periodicity. Memoization handles this efficiently.

    # Set to store Grundy values of states reachable from L
    reachable_grundy_values = set()
    
    # Consider possible moves based on game rules:

    # Operation 1: Choose an isolated empty square ('E' surrounded by 'O' or boundaries) and place a sushi plate.
    # This operation is only possible for a segment of length L=1.
    # The segment 'E' becomes 'O', which corresponds to a segment of length 0.
    if L == 1:
         reachable_grundy_values.add(calculate_grundy(0)) # G(0) = 0 is the Grundy value of the resulting state.

    # Operation 2: Choose 3 consecutive empty squares ('EEE') and place sashimi plates on 2 adjacent squares.
    # This operation is possible for segments of length L >= 3.
    # 'k' represents the 1-based starting index of the 'EEE' block within the segment. k ranges from 1 to L-2.
    elif L >= 3:
      for k in range(1, L-2 + 1): 
          # Option 2a: Place plates on squares k and k+1. The state becomes 'OOE'.
          # This splits the original segment L into two new segments (possibly empty):
          # Left segment: squares 1 to k-1. Length k-1.
          # Right segment: squares k+2 to L. Length L - (k+2) + 1 = L - k - 1.
          # The Grundy value of the resulting state is the XOR sum of the Grundy values of the two new segments.
          reachable_grundy_values.add(calculate_grundy(k-1) ^ calculate_grundy(L-k-1))

          # Option 2b: Place plates on squares k+1 and k+2. The state becomes 'EOO'.
          # This splits the original segment L into two new segments:
          # Left segment: squares 1 to k. Length k.
          # Right segment: squares k+3 to L. Length L - (k+3) + 1 = L - k - 2.
          # The Grundy value of the resulting state is the XOR sum.
          reachable_grundy_values.add(calculate_grundy(k) ^ calculate_grundy(L-k-2))

    # If L=2 ('EE'), no moves are possible. Reachable set is empty.

    # Compute the Minimum Excluded value (mex) from the set of reachable Grundy values.
    mex = 0
    while mex in reachable_grundy_values:
        mex += 1
    
    # Store the computed Grundy value for L in the memoization table.
    memo[L] = mex
    return mex

# Precompute Grundy numbers up to PRECOMPUTE_LIMIT using iterative approach.
# This ensures that all values needed for periodicity calculations are available.
memo[0] = 0
for i in range(1, PRECOMPUTE_LIMIT):
    # calculate_grundy(i) computes and stores G(i) into memo dictionary.
    # It relies on G(0)...G(i-1) already being computed and stored.
    calculate_grundy(i) 

# Main function to read input and determine the winner
def solve():
    # Read N and K
    N, K = map(int, sys.stdin.readline().split())
    
    # Read initial sushi plate positions
    A = []
    for _ in range(N):
        A.append(int(sys.stdin.readline()))
    
    # Problem statement guarantees A_1 < A_2 < ... < A_N, so A is already sorted.

    # Calculate the Nim-sum (XOR sum) of Grundy values for all segments of empty squares
    nim_sum = 0

    # Calculate length of the first segment (from square 1 to A[0]-1)
    length1 = A[0] - 1
    nim_sum ^= calculate_grundy(length1) 

    # Calculate lengths of segments between consecutive sushi plates A[i] and A[i+1]
    for i in range(N - 1):
        length_mid = A[i+1] - A[i] - 1
        nim_sum ^= calculate_grundy(length_mid)

    # Calculate length of the last segment (from A[N-1]+1 to K)
    length_last = K - A[N-1]
    nim_sum ^= calculate_grundy(length_last)

    # Determine the winner based on the Nim-sum.
    # If Nim-sum > 0, the first player (Yes) has a winning strategy.
    # If Nim-sum = 0, the second player (No) has a winning strategy.
    if nim_sum > 0:
        print("Yes")
    else:
        print("No")

# Execute the main function
solve()
0