結果

問題 No.93 ペガサス
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:22:01
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,859 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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()
0