結果

問題 No.2986 Permutation Puzzle
コンテスト
ユーザー ID 21712
提出日時 2025-04-17 16:26:41
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 2,717 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 106,188 KB
最終ジャッジ日時 2025-04-17 16:26:46
合計ジャッジ時間 4,236 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1 -- * 1
other -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

# this code was generated by grok 3 beta (x.com)

def inverse_permutation(perm):
    # 順列の逆順列を計算（1-based）
    n = len(perm)
    inv = [0] * n
    for i in range(n):
        inv[perm[i] - 1] = i + 1
    return inv

def apply_row_perm(matrix, perm):
    # 行を指定された順列に基づいて並び替える
    n = len(matrix)
    new_matrix = [None] * n
    for i in range(n):
        new_matrix[i] = matrix[perm[i] - 1][:]  # 行 perm[i] を i 番目に
    return new_matrix

def apply_col_perm(matrix, perm):
    # 列を指定された順列に基づいて並び替える
    n = len(matrix)
    new_matrix = [[0] * n for _ in range(n)]
    for j in range(n):
        target_col = perm[j] - 1  # 列 perm[j] を j 番目に
        for i in range(n):
            new_matrix[i][j] = matrix[i][target_col]
    return new_matrix

def check_equal(matrix1, matrix2):
    # 2つの行列が等しいか確認
    return all(row1 == row2 for row1, row2 in zip(matrix1, matrix2))

def solve(N, K, A, B):
    # 反復深さ優先探索で B から A への操作列を探索
    from collections import deque
    stack = [(B, [])]  # (現在の行列, 操作列)
    limit = 1000  # 操作回数の上限
    visited = set()  # 訪れた行列のハッシュ

    while stack:
        current, operations = stack.pop()
        if len(operations) > limit:
            continue
        if check_equal(current, A):
            return operations

        # 行列をハッシュ化（訪問済みチェック）
        matrix_hash = tuple(tuple(row) for row in current)
        if matrix_hash in visited:
            continue
        visited.add(matrix_hash)

        # 各行を試す
        for i in range(N):
            perm = current[i]
            inv_perm = inverse_permutation(perm)  # 逆順列で並び替え
            new_matrix = apply_row_perm(current, inv_perm)
            new_ops = operations + [("R", i + 1)]
            stack.append((new_matrix, new_ops))

        # 各列を試す
        for j in range(N):
            perm = [current[i][j] for i in range(N)]
            inv_perm = inverse_permutation(perm)  # 逆順列で並び替え
            new_matrix = apply_col_perm(current, inv_perm)
            new_ops = operations + [("C", j + 1)]
            stack.append((new_matrix, new_ops))

    return []  # 解が見つからない場合（問題保証により発生しない）

# 入力処理
N, K = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
B = [list(map(int, input().split())) for _ in range(N)]

# 解を求める
ops = solve(N, K, A, B)

# 出力
print(len(ops))
for op_type, pos in ops:
    print(f"{op_type} {pos}")
0