結果
| 問題 |
No.1016 三目並べ
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:33 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 8,862 bytes |
| コンパイル時間 | 301 ms |
| コンパイル使用メモリ | 82,160 KB |
| 実行使用メモリ | 683,944 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:34 |
| 合計ジャッジ時間 | 4,572 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 6 MLE * 1 -- * 3 |
ソースコード
import sys
# Increase recursion depth limit for potentially deep game trees.
# This might be necessary if the number of empty cells (k) is large.
# The maximum recursion depth could theoretically be k, up to N=1000.
# Setting it to 2048 should be sufficient for moderate k values.
try:
# Set a higher recursion depth limit. Note: this might not work on all platforms
# or might be disallowed in some contest environments.
sys.setrecursionlimit(2048)
except Exception as e:
# If setting recursion depth fails, we can optionally print a warning to stderr.
# print(f"Warning: Could not set recursion depth limit: {e}", file=sys.stderr)
pass # Continue with the default limit if setting fails.
# Global dictionary for memoization. Stores results of subproblems (game states).
# Keys are tuples (board_tuple, is_O_turn), values are boolean (True if O can win, False otherwise).
memo = {}
def check_win_condition(board_str):
"""Checks if the board string contains three consecutive 'o's ('ooo')."""
return 'ooo' in board_str
# The core recursive function implementing minimax with memoization.
def recursive_can_O_win(board_tuple, is_O_turn):
"""
Determines if player O can force a win from the given board state and turn.
This function uses minimax logic assuming optimal play from both sides.
Args:
board_tuple (tuple): The current state of the board represented as a tuple of characters.
Tuples are used because they are hashable and can be dictionary keys.
is_O_turn (bool): True if it's player O's turn, False if it's player X's turn.
Returns:
bool: True if player O can force a win from this state, False otherwise.
"""
# Create a unique key for the current game state (board configuration + whose turn).
state_key = (board_tuple, is_O_turn)
# Check if the result for this state is already computed and stored in memo.
if state_key in memo:
return memo[state_key]
# Convert tuple back to string for easier substring checks.
board_str = "".join(board_tuple)
N = len(board_tuple) # Length of the board
# Base Case 1: Check if 'ooo' already exists on the board.
# If 'ooo' is present, player O has already won (or secured a win). This is a terminal state.
if check_win_condition(board_str):
memo[state_key] = True # Store result
return True
# Find all empty cells represented by '-'.
empty_indices = [i for i, char in enumerate(board_tuple) if char == '-']
# Base Case 2: If there are no empty cells left and 'ooo' condition was not met above,
# the game ends, and player O has not won. Thus, player X wins.
if not empty_indices:
memo[state_key] = False # Store result
return False
# Identify "critical" cells for player O.
# A critical cell is an empty cell where placing 'o' would immediately create "ooo".
critical_indices = []
for i in empty_indices:
is_critical = False
# Check if placing 'o' at index i completes 'ooo' pattern:
# Pattern 'oo-' becomes 'ooo'? Check cells i-2, i-1. Need S[i-2]=='o' and S[i-1]=='o'.
if i >= 2 and board_tuple[i-2] == 'o' and board_tuple[i-1] == 'o':
is_critical = True
# Pattern 'o-o' becomes 'ooo'? Check cells i-1, i+1. Need S[i-1]=='o' and S[i+1]=='o'.
elif i >= 1 and i+1 < N and board_tuple[i-1] == 'o' and board_tuple[i+1] == 'o':
is_critical = True
# Pattern '-oo' becomes 'ooo'? Check cells i+1, i+2. Need S[i+1]=='o' and S[i+2]=='o'.
elif i+2 < N and board_tuple[i+1] == 'o' and board_tuple[i+2] == 'o':
is_critical = True
if is_critical:
critical_indices.append(i)
# Minimax logic based on whose turn it is:
if is_O_turn:
# O's turn (Maximizing player for O's win)
# Check if O has an immediate winning move (a critical cell).
if critical_indices:
# If O can play in a critical cell, O plays it and guarantees 'ooo' on the board. O wins.
memo[state_key] = True
return True
# If no immediate win, O explores all possible moves.
# O wants to find at least ONE move that leads to a state from which O can win.
can_win = False # Assume O cannot win initially for this path
for i in empty_indices:
new_board_list = list(board_tuple) # Convert tuple to list for modification
new_board_list[i] = 'o' # O places 'o'
new_board_tuple = tuple(new_board_list) # Convert back to tuple for recursive call and memo key
# Recursively call for the next state (X's turn). If the recursive call returns True,
# it means O can force a win after making this move.
if recursive_can_O_win(new_board_tuple, False): # Pass turn to X
can_win = True
break # O found a winning move, no need to explore further moves for O.
memo[state_key] = can_win # Store the result for this state
return can_win
else: # X's turn (Minimizing player for O's win / Maximizing player for X's win)
# Check if O has created a "fork" (multiple critical cells).
if len(critical_indices) >= 2:
# If O has two or more immediate winning moves, X can only block one.
# O will play in another critical cell on the next turn and win.
memo[state_key] = True
return True
# Check if O has exactly one immediate winning move.
if len(critical_indices) == 1:
# X MUST block this single critical cell to prevent O from winning immediately.
i = critical_indices[0]
new_board_list = list(board_tuple)
new_board_list[i] = 'x' # X plays 'x' to block
new_board_tuple = tuple(new_board_list)
# Check the outcome after X blocks. The result of the recursive call determines the outcome.
result = recursive_can_O_win(new_board_tuple, True) # Pass turn back to O
memo[state_key] = result
return result
# If O has no immediate winning moves (no critical cells), X explores all possible moves.
# X wants to find at least ONE move that leads to a state where O CANNOT win (X wins).
# From O's perspective: O can win from this state only if for ALL moves X makes, O can still win.
can_O_win_overall = True # Assume O wins, unless X finds a move to refute this.
for i in empty_indices:
new_board_list = list(board_tuple)
new_board_list[i] = 'x' # X places 'x'
new_board_tuple = tuple(new_board_list)
# Recursively call for the next state (O's turn). If recursive call returns False,
# it means O cannot force a win after X makes this move. X has found a winning path.
if not recursive_can_O_win(new_board_tuple, True): # Pass turn to O
can_O_win_overall = False
break # X found a move that ensures X wins. No need to explore further moves for X.
memo[state_key] = can_O_win_overall # Store the result for this state
return can_O_win_overall
# Main function to handle input/output and test cases.
def main():
# Read the number of test cases.
T = int(sys.stdin.readline())
results = [] # List to store results for each test case.
for _ in range(T):
# Read N and the board string S for each test case.
line = sys.stdin.readline().split()
# N = int(line[0]) # N is board size, also len(S). We mainly use len(S).
S = list(line[1]) # Convert string S to list of characters for easier manipulation if needed.
# Convert board state list to tuple for use as dictionary key in memoization.
board_tuple = tuple(S)
# Clear the memoization dictionary for each new test case as they are independent.
memo.clear()
# Check if the initial board already contains 'ooo'. If so, O wins immediately.
if check_win_condition("".join(S)):
results.append("O")
continue # Move to the next test case.
# If no initial win, start the recursive minimax search.
# The game always starts with O's turn according to the problem statement.
if recursive_can_O_win(board_tuple, True): # Start with O's turn.
results.append("O") # O can force a win.
else:
results.append("X") # O cannot force a win, so X wins.
# Print all results, each on a new line.
# Using '\n'.join is efficient for printing multiple lines.
print('\n'.join(results))
# Standard boilerplate to run the main function.
if __name__ == '__main__':
main()