結果
問題 |
No.93 ペガサス
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:22:01 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,859 bytes |
コンパイル時間 | 264 ms |
コンパイル使用メモリ | 82,616 KB |
実行使用メモリ | 84,760 KB |
最終ジャッジ日時 | 2025-05-14 13:24:17 |
合計ジャッジ時間 | 7,697 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | TLE * 1 -- * 15 |
ソースコード
MOD = 10**9 + 7 # N_val will store N # p_val will store the current permutation (p_val[row] = col) # used_cols_val will be a boolean array to keep track of used columns # ans_counter_val will store the count of valid configurations # These will be treated as global-like variables for the recursive function _N_val = 0 _p_val = [] _used_cols_val = [] _ans_counter_val = 0 def is_safe_knight_interaction(k_curr, c_curr, r_prev, c_prev): """ Checks if the piece at (k_curr, c_curr) and (r_prev, c_prev) can coexist. k_curr is the current row, c_curr is the current column. r_prev is a previous row (r_prev < k_curr), c_prev is its column. Attack definition based on "Directed Shogi Knight Moves" to match N=4 -> 8: A piece at (R, C) attacks (R-2, C-1) and (R-2, C+1). "Mutually non-attacking": 1. (k_curr, c_curr) must not attack (r_prev, c_prev). This means (r_prev, c_prev) is NOT among {(k_curr-2, c_curr-1), (k_curr-2, c_curr+1)}. So, NOT (r_prev == k_curr - 2 AND abs(c_curr - c_prev) == 1). 2. (r_prev, c_prev) must not attack (k_curr, c_curr). This means (k_curr, c_curr) is NOT among {(r_prev-2, c_prev-1), (r_prev-2, c_prev+1)}. So, NOT (k_curr == r_prev - 2 AND abs(c_prev - c_curr) == 1). This second condition is impossible because r_prev < k_curr, so k_curr cannot be r_prev-2. Thus, only the first condition matters. """ if r_prev == k_curr - 2 and abs(c_curr - c_prev) == 1: return False # (k_curr, c_curr) attacks (r_prev, c_prev) return True def backtrack(k): # k is the current row index (0 to N-1) global _N_val, _p_val, _used_cols_val, _ans_counter_val if k == _N_val: _ans_counter_val = (_ans_counter_val + 1) % MOD return for c in range(_N_val): # Try column c for row k if _used_cols_val[c]: continue # Rook column constraint: column c already used # Check knight constraint with previously placed pieces # Piece to be placed: (k, c) # Previous pieces: (r_prev, _p_val[r_prev]) for r_prev from 0 to k-1 safe_from_all_knights = True for r_prev in range(k): if not is_safe_knight_interaction(k, c, r_prev, _p_val[r_prev]): safe_from_all_knights = False break if safe_from_all_knights: _p_val[k] = c _used_cols_val[c] = True backtrack(k + 1) _used_cols_val[c] = False # _p_val[k] = -1 # Not strictly necessary, will be overwritten def solve(): global _N_val, _p_val, _used_cols_val, _ans_counter_val N = int(input()) _N_val = N _p_val = [-1] * N _used_cols_val = [False] * N _ans_counter_val = 0 backtrack(0) print(_ans_counter_val) solve()