使用Python实现Kattis/UVA10404巴什博弈（Bachet's Game）时遇到的奇怪超时（TLE）问题

Hey there! Let's tackle this Bachet's Game TLE issue in Python. The core problem here is that Python's loops are inherently slower than C's, so we need to optimize both the algorithm's constant factors and the code's efficiency to get it past the time limits. Let's break down the optimizations step by step:

1. Optimize Input Handling #

Your current input method reads all lines at once and splits each line individually, which adds unnecessary string processing overhead. Instead, read the entire input as a single stream of tokens—this is much faster in Python:

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        group = list(map(int, data[ptr+2:ptr+2+m]))
        ptr += 2 + m
        
        # Rest of your logic here

2. Preprocess the Move Set #

Your original group may have duplicate values or numbers larger than n (which are useless since you can't take more stones than exist). Cleaning this up reduces the number of iterations in your inner loop:

# Deduplicate and filter out moves larger than n
unique_group = list(set(group))
valid_moves = [j for j in unique_group if j <= n]
# Sort moves in reverse order—this lets us find a winning move faster (break earlier)
valid_moves.sort(reverse=True)
# Create a set for O(1) lookups later
move_set = set(valid_moves)

3. Use a More Efficient DP Array #

Python's list of booleans uses more memory and is slower to access than a bytearray, which stores each value as a single byte. This small change adds up for large n:

# dp[k] = 1 means Stan wins with k stones left, 0 means Ollie wins
dp = bytearray(n + 1)

4. Optimize the DP Calculation #

We can skip redundant checks by:

• Marking all positions where Stan can win immediately (taking all remaining stones) upfront
• Starting our loop from the smallest valid move, since positions smaller than that are automatically losing positions

if valid_moves:
    min_move = min(valid_moves)
    # Positions smaller than min_move are losing positions (already 0 in bytearray)
    for k in range(min_move, n + 1):
        # If k is a valid move, Stan can take all stones and win
        if k in move_set:
            dp[k] = 1
            continue
        # Check if any move leads to a losing position for Ollie
        for j in valid_moves:
            if k >= j and dp[k - j] == 0:
                dp[k] = 1
                break
    # For k < min_move, dp[k] remains 0 (Ollie wins)

5. Avoid Unnecessary Output Overhead #

Your original code prints with an extra "\n" at the end. Instead, use print("Stan wins") directly—Python adds a newline by default, and this cuts down on minor output overhead.

Putting It All Together #

Here's the full optimized code:

import sys

def main():
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])
        m = int(data[ptr+1])
        group = list(map(int, data[ptr+2:ptr+2+m]))
        ptr += 2 + m
        
        # Preprocess moves
        unique_group = list(set(group))
        valid_moves = [j for j in unique_group if j <= n]
        valid_moves.sort(reverse=True)
        move_set = set(valid_moves)
        
        dp = bytearray(n + 1)
        
        if valid_moves:
            min_move = min(valid_moves)
            for k in range(min_move, n + 1):
                if k in move_set:
                    dp[k] = 1
                    continue
                for j in valid_moves:
                    if k >= j and dp[k - j] == 0:
                        dp[k] = 1
                        break
        
        print("Stan wins" if dp[n] else "Ollie wins")

if __name__ == "__main__":
    main()

Why This Works #

• Input optimization: Reading all tokens at once minimizes slow I/O operations.
• Move preprocessing: Reducing the number of moves we check per iteration cuts down loop time significantly.
• Bytearray: Uses less memory and faster access than a list of booleans.
• Early termination: Sorting moves in reverse order lets us break out of the inner loop as soon as we find a winning move, avoiding unnecessary checks.

Edge Cases to Verify #

Make sure you test these scenarios:

• All moves are larger than n (Ollie wins)
• n equals one of the valid moves (Stan wins immediately)
• Multiple duplicate moves (our deduplication handles this)
• n = 1 with a valid move of 1 (Stan wins)

内容的提问来源于stack exchange，提问作者Kyros